Well It shouldn't sound like 4 kHz, but I would expect it to sound like 8 kHz as this is the telephony standard for now (except for some proprietary VoIP services like Skype).
If you have a 22 or 44 kHz sound file and you down-sample it to 8 kHz, I find that it sounds a lot worse than if the original composition was made for 8 kHz playback (This is also true for text to speech and why many TTS companies will offer both a 22 and 8 kHz version of their voices).
Lastly, if you are using the GSM codec, you will get cell-phone like quality & audio compression. You will find that using the G.711 codec which is basically uncompressed, provides much better quality audio. There is a trade-off however... If I remember correctly, GSM only uses about 5 kbps of bandwidth whereas G.711 uses something like 80 kbps (and I think that's just 1 way, x2 for up & down bandwidth).