Actually it’s now working and I’m not sure which change fixed it! During various tests I had ticked the box that archives images by date. After the upgrade to WP3.0.1 and a test to try uploading a header (which still threw up the same error message as yesterday) I decided to untick the option to store images by date. Then I went back to the header and was able to successfully upload it!
Well, that’s a relief anyway.
Edit: The uploads folder is still set to 777. I tried changing it back to 755 but got the error again. I guess I’ll have to keep it at 777.