My host (Intimidated from sharelive.com) gave me this solution:
find the file in question (which was gallery/include/picmgmt.inc.php)
Add these lines to the top of the file
set_time_limit(6000);
ini_set('memory_limit', "640M");
As long as your host doesn't restrict memory limits (he says that a lot don't, but the values are defaulted low), this will make it work.
Worked for me beautifully.
Sorry if this is in the wrong section
This will work if you can run ini_set BUT on the other hand if a shared server is allowing ini_set I would say the server is very poorly configured. :)