Well, 128k sounds like complete crap, even on bad speakers, or in a moving car. First - use LAME and not Xing, Xing at 320 sounds about the same as LAME at 224, and has other problems too (Like all response over 14 or 15Khz is just a garbled mess of distiortion).
The biggest difference between a 128k mp3 and the original will be the quantization noises. To an untrained but aware ear, it just sounds like distorted treble. But - they are basically artifacts that come out of the compressed sound, because it is approximated, it almost sounds like birds chirping on particularly bad recordings, is harsh, grating, and evry unplesant. It isn't distortion, but actually added junk noise into the sound.
The second biggest difference is bass performance. You definantly won't notice this on your computer speakers, but on my speakers and headphones the difference is very clear. My biggest example track for this would be Enya's Sail Away, at the beginning of the song the bassline is something to the effect of pizzacato strings and an accompanying synth line or something, and I have 2 mp3s of it that I have downloaded. One is a 224k MP3, and the other a 128k one. The first thing I notice on a casual listen is that the low quality version sounds bright, it almost sounds arier then the regular version. When Enya starts singing, her voice has what first seems to almost be a garbly edge. Slightly more careful listening shows this brightness is actually basically semi-random high frequency sounds, and the edge on her voice has more, lower versions of the same - it just sounds garbled.
The second is the amount of impact the bass line is lacking - in the 224k one, the bass is much more pronounced (This is midbass/deep bass), to a very large degree. I am talking about something I can really feel the difference in with headphones at a normal listening level, and through speakers the difference you feel is more noticable but hear is less noticable. Note that exxagerating the bass a little bit basically makes up for the thin sound of the low quality mp3s.
As you go to higher quality mp3s, these quantization noises get a lot less prominent, but are still there. Casual listening to a 192k mp3 just results in a slightly harsh sound to my ears. More closely, the same noises that plauge 128k are there, but are much much more subtle. Silibance is less of a problem then 128k, but is quite bad compared to CD quality on a good recording. 192k also has a somewhat grainy sound.
256k is naturally even harder to tell the difference with versus CD, but somtimes it is still clear, to an experienced listener. Silibance is slightly exxagerated, on complex passages quantization sounds can still be notably audible, and while bass performance is much better then lower quality mp3s, it still isn't quite as full as CD.
96k mono/32Khz I like more then 128k/44Khz stereo, simply because there are much less quantization noises present. Sure, the sound is a bit thin and of course lacks ambience, air, and treble extension, but the sound is just so much cleaner then 128k/44Khz stereo it isn't even funny.
So, the bottom line is that I have a few 96k mp3s that are listenable (music), ranging to 192k mp3s that are unplesant, and 256k mp3s I am quite unsatisfied with.