I've used the CCCP for years now. It is by far, the best playback solution I've ever tried, and it keeps getting better with each new release. And if you think there's something borked with the install, or something else might be interfering, use the Insurgent tool to check for other packs.
Also, for the record, before I stumbled upon it all that time ago, I loathed codec packages like the plague. Almost every single one included bloatware, spyware, or other unwelcome software included. The CCCP however, is different. It was written so that the anime fansub community would have a single, working, playback solution so that they could stop having to field support questions like 'how do I playback .mkv's?', etc etc etc. It's not even technically a codec pack, since as far as I can tell, all it does is install a bunch of directshow filters, and then installs the pre-configured software player of your choice, set up to use those filters.http://www.cccp-project.net/wiki/index.php?title=FAQ#What_is_CCCP.3F
One side effect is almost everything works in windows media player, as well.
Given that it's a bunch of directshow filters, you might try updating directx and see if that has any effect.
Barring all else, try using the revo uninstaller to uninstall the CCCP, purge all the registry entries for it, and then reinstall it from the (relatively) clean slate.http://www.revouninstaller.com/
Note that, if you don't want to use the revo uninstaller, CCleaner can also purge the registry entries. Just run its registry tool after uninstalling the CCCP.