Yeah, both a noise gate and noise reduction can mess with your tone.
I use a noise gate when dealing with an instrument such as a kick drum that has a clear ending to the notes. You have to mess with the controls of the gate (attack, release, hold, threshold) to get the optimum sound, trying to capture the full sound of the instrument while reducing the extraneous noises and bleed from other instruments. Of course, gates can be used creatively to give a track a really "tight" sound.
Noise reduction uses a noise sample (a part of the track containing only noise). It then flips the phase of the noise, and combines it with the entire section that you are working on. This CAN be useful for getting rid of unwanted backgroud noise that is very steady throughout a track (such as hum from a guitar amp), but you have to do some critical listening as it can really mess with your sound, and always in a bad way.
I've used noise reduction to get rid of computer fan noise, and I couldn't detect any change in the sound (using Cool Edit Pro's built in noise reduction), but most guys will tell you to avoid noise reduction software altogether unless you're doing a restoration project.