A quick checklist for myself, because this problem nearly always seems to occur on a fresh WordPress install, and it’s easy to forget what works!
1. Create the uploads folder yourself, in lowercase – “uploads” not “upLoads”
2. upload this folder to the wp-content folder
3. change the uploads folder’s permissions to 777 (and temporarily change wp-content to 777 as well just to be sure)
4. go to settings > media and add the full url to the uploads folder into the “Full URL path to files” field.
5. upload an image
6. reset permissions for wp-content to what they were to start with.
No guarantees but it seems to work for me.
note: Since I originally put this up we have started using a different isp and the problem rarely occurs now, so the solution above is probably a solution for specific situations rather than across the board. However anything is worth trying if you’re stuck so I hope it’s useful to someone!