I had the exact same problems, with exactly the same size files on my old host. I take it you have tried setting the php.ini file, or altering the .htaccess file to greater values?