You can use Noiseware or something similar (Noise Ninja, etc.) to reduce the amount of noise, but the best thing to do is use a low ISO, and keep the camera cooled. With long exposures, the camera gets warm, and the warmer it gets the noisier it gets. The colored noise you have (reds, blues) are a result of heat in the camera. There's plenty of ways to keep the camera cool, one of which is a simple fan blowing on it. You might introduce a bit of vibration, but on a sturdy tripod you should be okay. Other options get a little bit more involved, like taking a styrofoam cooler and modifying it to fit around the camera and installing small fans.
You don't want to use in-camera noise reduction, it will add time to the exposure, and add more heat. In-camera noise reduction works at the same duration as your exposure, so if you have a 1 minute exposure, it takes a minute for the noise reduction to run. You've now extended your camera on-time to two minutes instead of one, which dds more heat, and more noise.
Run over to Cloudy Night astro forum, and ask there. There's a ton of great people there and a ton of useful info.