I just ordered a newer server and started moving sites over to it. Just now I tried to upload an image and kept getting failure messages in WordPress.
I FTPed in to check the permissions on the directories and everything looked good. I was also able to upload via FTP just fine.
That was when I remembered something about the last server I got through this hosting company.
For some reason their default PHP install is lacking a few things in the php.ini file. One of those things is the declaration of the /tmp directory for PHP uploads!
After a quick bit of vi editing I set the /tmp directory and increased the size of my uploads to 20MB.
I'm just glad i caught this right away. I would have been in a bind if this problem cropped up while I was not in a position to SSH into the server.