If your using GD try finding out if you have imagemagick installed and switch to that?
Has your host upgraded anything lately?
I can upload rather large files to your install fine http://www.justinternationals.org/ga...cat=500&page=1
so I am at a loss for suggestions to give you. If you cant give me one of there files to try I dont know what to do.