I agree that the initial culprits were in fact the several media players I toyed around with. I believe these media players attempt to make common file types their own, beyond just associating them as an "open with" scenario. Once you uninstall the media player, the OS thinks that this is no longer a used file type since the media player associated with it is uninstalled, hence CCleaner attempting to remove it as an unused file type.
Seems that Vista allocates file associations in several different parts of the registry, as opposed to confining it to one, easily identifiable area. CCleaner doesn't seem to analyze and corelate these different areas. Seems mostly like a Windows bug rather than a media player or CCleaner problem.
I believe the initial culprit was Winamp, which has had serious file association issues with XP and Vista across several versions. Once I uninstalled Winamp, a lot of common file types like .mp3, .m3u, .wav, etc. were deleted from the registry. Even after associating with a new media player, the correct registry keys were never re-written in Vista beyond the "Open With" keys.
It's a shame how one or two software instals/uninstal;s can corrupt registry items. That's why I use CCleaner but in this case it seems to only have made the problem worse.
Anyways, thanks for the help. A fresh Vista install and more careful software usage should solve the problem in the future.
PS- This forum seems to have an issue with email notification of responses. I signed up for them and am not getting them when anyone replies, not even in spam folder. Just thought I'd point that out as well.
Cheers