I had trouble uploading a few of my .mp3s to my Creative Zen Vision M and it didn't work. I contacted someone on the Zen boards and they said my tagging was corrupt on the file but couldn't provide an answer how to fix it. I'm not sure if I'm allowed to post a URL to my mp3 (ive got it hosted).....

Try using FooBar2000 to edit the tags. It has the ability to wipe out the existing tags and reconstruct them.
Another bit of freeware I know of is ID3-TagIT, found here http://www.id3-tagit.de/. I regret that I have not used it but a friend tells me that it is his favorite program to update his media and reconstruct broken MP3s.