Absolutely, Matt. A lot of people think that if they have an MP3 encoded at, say 128kbps, they can make it sound better by going 'up' in bitrate to 192, 256, 320kbps. Dead wrong, it only makes it worse as you said. Going down the ladder is the best way, and if you have a crappy 128kbps file, that's as good as it's gonna get, so do yourself a favor and just leave it alone.
Matt, if you're referring to Powermad's CD originals sounding like crap these days, I agree. I have the original "Absolute Power" CD, and if you compare it to even other CD's from that time, it's really weak. Whoever mastered it the first time 'round just compressed it to absolute 0-DB, with no deviation in the levels whatsoever. Mastering CD's was still a very new thing for engineers, even in the late 80's. At one point, a few years ago, Powermad were actually offering both albums as free downloads on their web site, at 320kbps MP3. They were transcoded up from 128kbps.
Sometimes bands transcode their files on purpose when offering them for free download so (some) bootleggers won't want to make and sell CD's, I think.
If you were talking about Sindrome, I'll have to check that out. Sounds like a good band.