This happens for me too. I don’t rate Photoshop’s conversion tool. Changing bit depth doesn’t seem to have much affect either.
Best solution:
**Download xNormal. Its free, and in the ‘Tools’ tab, there’s a heightmap to tangent normal map converter which works well. **