Hi there, i just have moved to another hosting and also have the SAME issue, they have Suhosin patch installed that blocks the taxonomy.php memory usage and generates that 500 error. Also Suhosin guys said this:
FreeBSD PHP2.5.1 version is buggy and needs to be updated to FreeBSD PHP2.5.1_2
They told me to add this lines to my .htaccess file:
zend.ze1_compatibility_mode Off
php_value memory_limit 32M
And IT WORKED!!!
I hope that this may help you.
Regards
ThePhoenixBird