Double check that your tonearm is properly zeroed, and that you have the appropriate tracking force and anti-skate dialed in.  (If your cartridge manufacturer gives a range instead of an optimum setting, start at about 75% of maximum).  Note: Do not use blank records or blank grooves to set the anti skate.  This gives you the setting that is correct only for this type record, not one that has music in the grooves!  The optimal anti-skate setting depends on the groove shape, the diameter of the groove at that spot on the record, and the modulation of the groove.  All you can hope for is the best compromise.  On most arms, setting the anti-skate the same as the tracking force, as the manufacturer intended, gives the best result.

Make sure your stylus is clean.  Brushes and liquids are all useless: When playing a record, a mix of vinyl, metal, and oil are pounded onto the stylus at high heat and at about 2.5 tons per square inch.  It takes something abrasive to get that junk off of there.  30 micron aluminum oxide paper (Linn stylus cleaning paper, made by 3M) is the best.  Very fine emery cloth ("Crocus cloth") or the strike pad from a matchbook will also work.  (Be warned that on some cartridges, the stylus is so poorly affixed to the cantilever that it will not survive a proper cleaning.)

Even if a stylus has been regularly cleaned as described above, there will be "gook" on the stylus well above that portion that touches the record.  It is necessary to hold the cleaner vertically and clean the stylus all the way up to the cantilever.  This takes a very delicate touch in order to avoid over-extending the suspension or bending the cantilever.

A record grove is a "V" shape.  The bottom is supposed to be a perfect point.  But often it is rather round, owing to worn molds, or debris in the bottom of the groove.  Modern styli are smaller than those on older players.  If it's a used record, especially if it has been played on an older "trench digger", the tip of the smaller, modern stylus may touch the bottom of the groove.  When this happens, the stylus no longer makes proper contact with the sides of the groove.  The result sounds really bad.  It is also possible that the groove has been damaged by an old player, and the current player is just reproducing that damage.  If you can find someone with a record cleaning machine, it might be worth cleaning the record to see if it helps.  (The only time I would clean a record is if it seems damaged or if it is terribly noisy, as my experience with a variety of cleaners and fluids is that the record always comes out quieter but it always sounds worse.)

Especially if you are using a moving coil cartridge, avoid record treatments.  I've had my hands on a lot of cartridges that were little worn, but sounded as though they were worn out, because they were clogged by innumerable shards of treatment potion that were shaved out of the groove by the stylus.  After having a good stylus cleaning and being blown out with compressed air, these cartridges sounded just fine.  In each of these cases, the few minutes that were spent cleaning the cartridge saved the owner hundreds of dollars.