I too have been struggling with this exact same problem for months. I cannot find a common thread of problems since some users are okay but they report many tries and long upload times. Other users give up and email me their images (for the free ads....)
I have looked at the php files in the routine and cannot see anything out of the ordinary. Is there another way to upload files with php? The issues seems to be some kind of lag since when they press the submit button, it sits on contacting
www.mysite.com in the status bar... like it is waiting for my server. When I open up a concurrent session to my server and request pages they are returned instantly.. no lag. I am convinced the problem is the scripts.
Any help from the gurus would be appreciated. I too have a solid ISP and solid hosting and the consistent problem is with simple uploads of 450k images (on average). It just seems to choke.