Experienced the same problem on several old sites. This problem occurs sporadically and is not commonly occuring on other websites on the same server
Try going to your "Media Settings" page... do you see a "Store uploads in this folder" option with a long path to your uploads folder? If so... this is your problem... WordPress 3.5+ does not seem to require this long path, but more of a site relative path (which is great!)
Change your "Store uploads in this folder" to "wp-content/uploads"... when you "save settings" you should see that field disapear entirely, never to bother us again ;-)
This occured for me when my hosting provider changed the folder structure on the server making this long URL incorrect. Therefore WordPress could not find the "uploads" directory at all.
Hope that helps...
Here's some things you might want to check in case your still having problems...
Update to WordPress 3.5 +
Update all plugins
Check file permissions 755 on the uploads dir/
Check PHP version