I contacted my host and they found the problem. Here’s their response:
I was able to resolve this error by disabling mod_security on the domain. Since we are unable to disable only the rule that is broken, the only solution was to disable mod_security altogether. I have tested an upload before and after disabling and it works now.
Are you able to upload small images? under 128k? I am having the HTTP error on 3 sites with 3.5.2. I did a completely fresh install and still could not upload any media greater than 128k w/o the error.