Sorry to open this again, but I'm having the same problem and the above fixes aren't working.
I've set both my post_max_size and upload_max_filesize to 30M. One of the files is only 2.5MB, but it still doesn't work.
The files actually upload fine, I can see them fine if I go directly to the location. But then if I try and view them either in the Gallery backend or in the frontend, it just doesn't work.
It feels like an issue with PHPThumb?