HAHAHA, I have installed RADIUM mp3 condec, the Nemo codec pack, the Kazaa Lite Codec pack, MWP codecs, and everything else I could possible image that had some form of mp3 codec in it.
Of course, I uninstalled each one of those as I relized they didn't fix the problem.
While cleaning out an old 10GB backup Hard drive, I found the LAME mp3 codec. LAME is a great encoding codec, but it's really hard to find a compiled source for it, since it's mostly used by Linix users.
Well, this was a compiles source (14K)

I installed it (which took about 2 seconds) and now MP3's and movies play fine!! Good old LAME.
I'll have to put it on the Yahoo briefcase in case of future problems and to help others since finding that compiled source was so hard.