HTTP Error on Image Upload

I recently moved a WPMU install to a new host (Comcast, which my client picked, lol) and am running into a strange issue when uploading to the media gallery.

If I try to upload a new version of an image already in the uploads folder, I'll get an HTTP Error message when trying to upload. If I just create a test file and upload it, the upload goes through with no error.

Funny thing is, I can look in the uploads folder and see the images I'm getting errors on. They do show up in the media library. But this error prevents me from using images in my Nivo Slider plugin I'm using.

I've tried increasing the memory for WP through the wp-config.php and .htacess files, but no luck with that so far. I've also tried disabling all plugins.

I'm not sure what else could be causing the issue. Does anyone have any ideas?