Yea, it really sounds like the cd player is upconverting cd's to maybe 192khz, which your tv can only get 44.1 and 48khz. I know you said you have tried everything, but try every setting again, maybe you will get it right. If the tv gets audio from dvd's, those have 48khz audio, so it's not a problem with the tv or the cd player itself, it must be an audio setting somewhere.
I have an old 5 disc cd player that I rarely use, but it automatically outputs digital audio from cd's in DTS format. I have to go into the options and disable that, and set it to only output 2 channel 44.1khz audio.