Was having trouble with 500 Internal Server Errors when uploading files larger than ~1MB and an inability to automatically upgrade WordPress. Did a lot of hunting around and none of the conventional solutions (increase limits in php.ini file, etc) seemed to apply. On a whim, I upgraded my hosting package to PHP5 and things magically started working. If you’re having this issue, hopefully this will work for you, too.
Also, for PHP5, my host (1and1) just requires that all php files end in .php5. Easy to accomplish in your .htaccess file, just add:
AddType x-mapp-php5 .php
AddHandler x-mapp-php5 .php
Best of luck!