JediTray, some things that come to mind (which you already may have thought of/taken care of), but just in case:

Are you using a MM or MC cartridge? Some phono preamps don't have enough output for an MC cartridge and you'll get A LOT of noise.

Also, if the preamp doesn't specify "phono" it won't have enough output to compensate for the phono's low level, and you'll get a lot of noise (unless your turntable has a built-in phono pre-amp then forget what I said about that). :-P

I use the same set-up Jetrell Fo uses (a CD recorder and turntable hooked up to a stereo receiver) and I've had great results.