Server upgrade, now unable to use automatic updates

My webhost recently moved the site to a different server running PHP 5 (the old one was PHP 4 and we were having repeated issues). Since the upgrade, however, I have been unable to use the automatic update function for either WP or plugins.

Attempts to use automatic update result in a long (+/- 6 minute) wait and then a 500 error message. “Requested URL causes an internal server error.”

The rest of the site works fine.

I have tried disabling all plugins and re-activating one by one without result. I have not tried switching the theme but will do that next. One piece of advice I saw was to add “memory=20MB” to the php.ini file but I’m not counting on that to work.

Any suggestions greatly appreciated!