The "faster" the lens (lower aperture[f] number), the better it will do in low light, however, with a flash, you should have been fine with just about any lens. The SB-600 is a very solid flash and if you were still having issues, then it sounds like a metering problem. I would suggest trying different metering modes, make sure that you are using iTTL metering and if necessary adjust exposure compensation.
I'm not sure if Nikon's behave the same way, but if they place limits on the ISO, it might be worth manually setting to a higher ISO as well. With my Canon camera, at ISO 1250 and using a 600EX flash (the equivalent of the SB-800), I've taken telephoto photos in very dark environments from up to 70 feet away without a problem and gotten good exposure with fairly minimal noise, though I was also using a high end f/2.8 lens at the time.
If metering doesn't fix it (though I think it will), the best options are faster lenses or more light. You could use a larger flash or an additional off camera flash, though you would need a master control unit for firing the remote flashes. As far as faster lenses, an f/2.8 lens can normally be obtained pretty cheaply as a prime lens and should generally be sufficient for most low light cases(though faster is always better).
You can also try turning up the ISO further. While this increases noise, it should increase noise slightly less than having to artificially boost a dark image after the fact as it limits the sources of noise that can occur prior to the gain. If the image is dark all the way through processing, then additional noise can be added by the noise floors that are present after the gain for the ISO is applied.