Upon upgrading my hosting, I found my old friend the HTTP error was back when uploading images that exceeded certain dimensions. I could resize images smaller on my desktop and then they’d upload just fine but that was a lot more cumbersome and made WordPress lose some of its slickness.
Upon looking into the problem further, I found a very comprehensive list of troubleshooting steps to take on the WordPress Support Forums. The thread, Image/Media Uploader problems?, might be two years old but it’s still relevant and solved my problem. For the record, implementing step 6 resolved my issues.
Big thanks to Otto of Ottopress.com for posting that thread back in the day.