This error just cropped up for the first time for me last night.
I decided to try an experiment. I found that if I uploaded my mp3 to Cloudfront without any ID3 tags, the file would verify with no errors. I then added data into the ID3 tags (BTW, I use iTunes 11.4 to do this, on OS X 10.8.5) one field at a time, re-uploading after each change. After adding Title, Artist, Album Artist, Album, Comments, Genre and Media Kind, I got no errors. It was only after adding my artwork (1400x1400) that the error occurred.
Any ideas?