Some host companies (like 1and1) run both PHP 4.x and 5.x and default to 4.x. You may need to have an .htaccess file that ensures you are using the correct version of PHP.
Also, the magic __toString() is slightly different from version 5.2+ according to the documentation:
It is worth noting that before PHP 5.2.0 the __toString method was only called when it was directly combined with echo() or print(). Since PHP 5.2.0, it is called in any string context (e.g. in printf() with %s modifier) but not in other types contexts (e.g. with %d modifier). Since PHP 5.2.0, converting objects without __toString method to string would cause E_RECOVERABLE_ERROR.
So, it may depend on how you are calling the output.