Buy a new cartridge. It sounds like you are using a cartridge which is too low output for your preamp. Was the cartridge bought new? If so, I would hope your dealer asked you what preamp you are using.
If you do have a preamp for moving magnet cartridges, you will have to get a moving magnet cartridge, or a high output moving coil cartridge. I know the grado high output moving coil cartridges are fine with a moving magnet phono stage.