Any valid mp3 ALWAYS works after dragging it onto iTunes Associator and then dragging it onto Quicktime or into the iTunes window (note that I say drag NOT double-click).

If this doesn't work, it means that the mp3 is corrupted. I have never got any mp3s that didn't work using this method to work with any other. There have been several reports that there are a lot more scam/corrupted mp3 files on Gnutella (some placed there by record labels) so that could be a reason why fewer are working - especially if you are downloading commercial Top 40 tracks.

As a last ditch effort, you could try downloading another player like Macamp or Audion (do a Google search) and see if they work. You could even try burning the files onto an ISO 9660 (PC format) CD and trying them on a friend's Wintel machine.

I'm sorry I can't suggest anything else, but I've never had any problems playing back mp3s using the methods I've described (apart from corrupted files).