What are you using to play back the songs? WinAmp?

Does this happen with any other MP3s or just with ones downloaded with Gnotella?

Is there anything else on your computer that is hogging CPU time?

Are you downloading most of your songs from the same server? Sadly, some people don't know squat about encoding MP3's. They either encode at too low a volume, too high a volume or they think they can run Unreal Tournament, scan a document, fax and crunch a spreadsheet AND encode a MP3 all at the same time. If the CPU gets overloaded by other things, the quality of the MP3 will suffer because the encoder is constantly being interrupted by all the other competing tasks. I always treat encoding the same way as CD-burning, shut down other programs first and JUST do encoding!