It could be in your phono cartridge, in the interconnect from table to phono amp or from the phono amp to the preamp. Only way to tell is to do some troubleshooting and minimize the variables via process of elimination. Sean
Other than the cartridge or the connections as already mentioned, the problem could also lie in the phono section itself as you speculate. Like Sean says, you'll have to do isolation/substitution testing on each variable to nail it down - no one here is going to be able to tell you where your gremlin resides from afar.
You may have a bad electrical connection in the little wires between the cartridge pin clips and the tonearm shaft or where the tonearm wiring is attached to the tonearm's signal socket (into which the interconnect cable to the phono preamp is plugged). Try gently moving the little wires near the cartridge back and forth between plays, and see if the problem gets worse or better. Try rotating the signal socket back and forth on its mounting also. If neither of these actions makes a difference, consider switching the left vs right channel connections at the cartridge pins to see if the problem is in the cartridge. Of course, it could be anything in your signal chain, as has already been mentioned. Good luck.
This sounds like a cartridge alignment, antiskate, azimuth, or tracking force problem as some of the others have suggested. To check that, you can go through the adjustments again, particularly the ones I've mentioned, or reverse the channels via the cartridge pins and see if the noise switches channels. If the noise switches channels, you'll know it's related to the cartridge. If readusting the cartridge settings doesn't cure it, then you may have a bad cartridge.
If the noise doesn't change channels when you switch the cartridge leads(I'm betting it will), then the problem is likely a bad connection somewhere between the arm wiring and the input to the phono stage.