Well - if PHP was not upgraded correctly ( which is what I think is the case ), then my suggestion is to upgrade it properly...Heh.
I know that on my server, running the latest version - file uploads work just fine.
Also, make sure the dirs on the server have not changed, if they have - your PHP script won't find the file it needs to move. If you're running a linux system, perhaps you need to chmod the directories again...
Something wasen't done properly, that you can be sure of.
Good luck, let me know how it turns out.
-Brad.