I'm having the exact same problems on my katiemay.net site, but not on GoDaddy hosting (I use Hostgator). Errors with both flash and browser media uploading. The errors I'm getting:
With Browser Uploading: "Error saving media attachment."
With Flash Uploading: "“xyz.jpg” has failed to upload due to an error
Unable to create directory /home/neptune/public_html/katiemay.net/wp-content/uploads/2011/04. Is its parent directory writable by the server?"
I am able to upload images via FTP to that exact folder (which I created manually with 755 permissions), but they do not show up in the Media Library. Permissions for those upload folders are all at 755. However, the image does not show up at the correct link (404 error), even though it looks fine in the FTP:
Meanwhile, images in similar upload folders (same permissions) from before work fine:
Not sure when exactly it began, but I think when I upgraded to 3.1. I've tried most of the adjustments given above, including upgrading any other potential conflicting plugins. I have some log info, but it just seems to show when it is being retrieved, not any of the error data.