Vixe, editei minha resposta.. Viajei na maionese, parece que li o enunciado e ele automaticamente foi embora da minha mente. Você colocou todas as classes na mesma pasta? Esse é um passo importante, para tirar proveito da visibilidade do modificador de acesso.

Estão na mesma pasta. O modificador protected é para as classes filhas conseguirem acessar o membro, e não as do mesmo pacote. PHP não tem esse modificador.

Oi Carlos, realmente o protected só libera o acesso da propriedade apenas para a classe mãe e as classes filhas. Portanto nesse caso seria necessário realmente o getter e o setter das propriedades saldo e estado porém o código ficaria com a seguinte estrutura.

<?php 
class Conta
{
    protected $saldo;
    protected $estado;

    public function __construct($saldo)
    {
        $this->saldo = $saldo;
        $this->estado = $saldo < 0 ? new Negativo($this) : new Positivo($this);
    }

    public function sacar($valor)
    {
        $this->estado->sacar($valor);
    }

    public function depositar($valor)
    {
        $this->estado->depositar($valor);
    }

     public function getEstado()
    {
        return $this->estado;
    }

    public function setEstado($estado) {
        $this->estado = $estado;
    }

    public function getSaldo()
    {
        return $this->saldo;
    }

    public function setSaldo($saldo) {
        $this->saldo = $saldo;
    }
}


<?php 
abstract class Estado
{
    protected $conta;

    public function __construct (Conta $conta)
    {
        $this->conta = $conta;
    }

    public abstract function sacar($valor);
    public abstract function depositar($valor);
}

<?php 
class Positivo extends Estado
{
    public function sacar($valor)
    {
        $this->conta->setSaldo($this->conta->getSaldo() - $valor);
        if ($this->conta->getSaldo() < 0)
            $this->conta->setEstado(new Negativo($this->conta));
    }

    public function depositar($valor)
    {
        $this->conta->setSaldo($this->conta->getSaldo() + $valor * 0.98);
    }
}

<?php 
class Negativo extends Estado
{
    public function sacar($valor)
    {
        throw new Exception('Esta conta está com saldo negativo');
    }

    public function depositar($valor)
    {
        $this->conta->setSaldo($this->conta->getSaldo() + $valor * 0.95);
        if ($this->conta->getSaldo() >= 0)
            $this->conta->setEstado(new Positivo($this->conta));
    }
}


<?php 
ini_set('display_errors', true);

require 'Conta.php';
require 'Estado.php';
require 'Negativo.php';
require 'Positivo.php';

$conta = new Conta(500);
echo $conta->getSaldo(), '<br />';
$conta->depositar(10);
echo $conta->getSaldo(), '<br />';
$conta->sacar(700);