Hmm! Very odd.
Can you try installing the "Force Regenerate Thumbnails" plugin?
I'll take a look at it, seems interesting.
Here's what happened though. I was trying to upload an image "image'1.jpg" that was failing. I tried uploading it to my other site, failed there too. So I tried to upload something different "image.2.jpg", which seemed to upload just fine - ummm, wtf?! That's when I realized, it was the damn ' in the file name. I renamed the first image to "image.1.jpg" and it uploaded just fine. Boy do I feel stupid
I wonder if the issues me as well as others had a year ago when uploading images had something to do with this.