As long as the 64bit Direct Show CoDecs show in the tweaker tool, 64bit Shareaza should be able to see/use them.
So maybe the K-lite pack need to be configured.
The tool has some ability to scan for errors and try to fix problems it finds. Perhaps try that.
When you have multiple CoDecs that can handle the same thing, often the most recently installed will take over.
The tweaker allows you to set the preferred codec, or use "Merit" to let Windows decide based on hard coded priorities.
Heh, looking at the tweaker site I see the tool is a standalone of some of the abilities in the K-Lite configuration.
Forget the standalone MPC Codecs if you are not geeky. They need to be registered manually as there is no installer.
They are exactly the same as you see in MPC with all the same config options, so handy if you like MPC (they are also quite small).
In your case I might suggest the FFDSHOW Codecs for an alternative to try.
http://www.free-codecs.com/download/ffdshow.htm