Did you make a NEW 16bit image, or did you just change the bit depth of the existing map? Wouldn't be the same thing. changing the bit depth wouldn't change anything, but making a new map would create twice as many pixels, which is what is needed here. And aslo, you may need a little gaussian blur added in PS to smooth the map out and avoid the effect you are seeing.