I know you're supposed to use mental ray for rendering ambient occlusion maps. But do you use mental ray for rendering normal maps, or do you use the default scanline renderer?
I'd guess you're using Max? I use the scanline renderer for both normals and AO. It's quicker for me to set up, it's quicker at rendering, and it usually yields better results. :)