Some encoders are crap, basically. I've come across AWFUL sounding MP3's at 192kbps. So bad I've had to chuck em! They had whistling in the high frequencies, distortion, all sorts of rubbish that the original "owner" obviously didn't notice/care about.
Not sure you can re-encode and actually gain quality. It doesn't really work like that. You'd need the original source.