These steps solved my uploading woes...
Firstly, on my test install, file uploads wouldn't work and I got the "HTTP Error". This was fixed with the addition to the .htaccess (in the top level of your Wordpress install).
I added the first four lines below to my .htaccess, so this is what I ended up with.
<IfModule mod_security.c>
<Files async-upload.php>
SecFilterEngine Off
SecFilterScanPOST Off
</Files>
</IfModule>
# BEGIN WordPress
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /index.php [L]
</IfModule>
# END WordPress
On my other install (Wordpress MU, but same idea), files would crunch, but then the directories could not be created or the file could not be move to that location.
This was because mod security is now installed. The uploads dir should no longer be given permissions 777, or given to user Apache. It should now be assigned to your username and group and folder permissions should be 755 and files 644 (that worked for me).
This will change the usergroup and username, and your host might have to do it for you (because files owned by Apache are not editable by users).
chmod -R yourusername:yourusergroup full/path/to/your/wordpress/upload/dir
If you don't know the dir, just tell your host it's the "wp-content/uploads" folder (or "wp-content/blogs.dir" for wpmu).