Yup, the darker the scene, the more likely it is you'll get noise at ANY ISO but especially higher ISOs. Also, exposure makes a big difference. If you don't expose properly, you'll be more likely to get noise. If you crop too much, you're more likely to get more noise. A lot of factors go into noise.
I looked at the various NR tools out there and settled on Noise Ninja. Nothing wrong with the others I looked at but it made more sense for me than the others. I'm very happy with it and I'm (finally) getting around to learning how to control it better. I do NOT like the default settings--makes it too smooth--so I back off them right away. Also, you have to be careful, one level down (or up) makes a big difference in what it'll do.
It eats noise like Pacman eats little white dots, fruit and blue ghosts....