Converting a 128kbps MP3 file into another lossy format is going to sound terrible.
At this rate, you're best off just re-ripping all of your CDs into a lossless codec (i.e. FLAC), and then transcoding to a lossy format (i.e. Vorbis).
Agreed
As long as it is encoded with LAME I'm happy with mp3's at 160, 128 or 96 kbps depending on which DAP my music is going on. I choose mp3 because of its universal compatibility, but I know I would probably be better off with Vorbis (V4 or V5) due to its smaller size and better efficiency. I just don't want to end up with several codecs on my DAP.
I am by no means an expert listener or stickler for quality, so I am alright with transcoding anything above a 192kbps mp3 to lower bitrates. I know this is a no no but I don't have a lot of my music in FLAC on my PC it is mostly 192k, ~256kVBR and 320k which I consider to be way too large for a DAP.
In the end it's what sounds acceptable to the listener, so take a CD and use something like mediacoder to rip to a few formats and see what you like.