Throw exception in favor of an error?
Well, I'd say that, apart from one or two things, you're going about it in exactly the right way.
A class, and all of its methods process data. If the data supplied poses an exceptional problem (ie, the data is invalid), then an Exception has to be thrown back to the code that passed that data.

The motto is: He who supplies the data, has to handle the errors.
By having methods simply return errors, your class is taking on too many responsibilities: Process data and error handling? No, that is in violation of the single most important SOLID principle: the SRP (Single Responsability Principle).

Here's why I am prepared to defend my statements on throwing exceptions from classes:


A class cannot check if the calling code is checking the return value of its method. You may return false or ERROR, but if the caller doesn't check it, you might aswell return a Shakespeare sonnet...
If you receive bad data, don't try to make sense of it, or don't try to make it work: the calling code has a bug in it, and should be fixed. The best way to spot the troubled bit of code is to throw new InvalidArgumentException and look at the stack-trace. Like I said before: bad arguments received often means bad code is calling your method: FIX IT.
If your class is well-tested, then it's safe to say that if ever it encounters a scenario where it can't do its job properly, something quite Exception-al has happened, treat it accordingly.
returning error-indicating values makes unit-testing harder, in a way. I, personally, like the odd @expectedException annotation, for example. If the test fails, it also yields more speceific output anyway.
You don't know what code is going to handle the problem. Returning an error-indicator is all well and good, provided that return value is caught, and indeed returned all the way through to the code that will eventually deal with it. An exception just keeps going until it is caught. If not, the whole application just grinds to a halt. Either way, returning false is less pressing, there's no real incentive to do something. An exception, however, must be handled for the program to go on.
You cannot register handlers for return false; or return null; statements, but you can register error and exception handlers. And you will do so in larger projects. This, certainly, is a huge advantage of exceptions.
Returning errors depending on the usage of your class limits the context/use-cases, in which you can use the class. A class should be a self-contained, portable unit of code. It should, therefore, just process data, or handle exceptional cases, not both.


Another quick hang-up of mine that I can't have go unmentioned: Please, please, please subscribe to the coding standards, as described by PHP-FIG.

Other niggles I have, and I'm really nit-picking here:

throw new Exception\TokenNotFound();


Ok, when I see this throw statement, I know that the TokenNotFound class is extending the Exception core-class (I hope), just like all other classes I might find in the Exception namespace. However, writing namespace Exception; at the top of a file could confuse PHP, if it doesn't already. Also, in files using the use keyword, the complementing catch statement just doesn't look right to me:

use Exception\TokenNotFound;
try
{
    //stuff
}
chatch(TokenNotFound $t)


Look at all Exception classes in common use: they all contain the word Exception (or Fault in SoapFault).TokenNotFoundcould be anything from a mock object, to a handler for just such an exceptional case, when in fact it is the exception object itself. Just appendException` to the exception class names. You may find this redundant at first, but at some point in time people using your code, or even yourself, will thank you for it.

use Exception\TokenNotFoundException;
try
{
    //stuff
}
chatch(TokenNotFoundException $t)