I am on WP 2.9.1, this did it for me also. I just added wp-content/uploads in the “Store uploads in this Folder” under settings -> miscellaneous …. eventhough it said this was the default.
The “Browser” upload method works now but The Flash Uploader still does not work in both WP Media Library and NextGEN Gallery.
Something else that was required just for the WP Media Library was the directory its trying to write to needed 777. My pictures were going into the “01” directory and changed this to drwxrwxrwx. When it was set to 775 it failed. Also the image files it uploading are getting set to rw-rw-rw-, 666. I imagin the other directories will need 777 as the month and year change.