Have you checked your attachments settings for the individual file types in the Admin CP?
Yes. I should have mentioned that earlier. Attachment sizes are set to max. I tried using different attachment size settings as well but had the same result.
To be honest, I'm not totally sure. But anything is worth a shot right now.
I have my max upload and max post both set at 64 MB and the memory at 128 MB (because I am on a VPS). Those settings should be way more than enough for anything I will have come through the site.