The artifacts on my image from due to the conversion from a JPG. I should have realized that right away.
Anyway, after playing with it a bit I think it's due to a combination of mapping issues and compression artifacts. The artifacts are there in all compressed images but you don't normally notice them unless you zoom in close. In this case the texture actually is zoomed it pretty close when applied, so you end up getting a seriously close up view of the artifacts. I was able to clean up the quality a bit by regenerating the normal map with various different settings, but the artifacts are still quite obvious. Basically this just seems like more of a mapping issue rather than a map issue.
Other than changing the mapping to fix the problem (which I can only assume would be more difficult):
1) Bump the map up to 4096x4096 to get to a high enough resolution to hide the artifacts (I tested it, looks pretty good)
2) Go with uncompressed DDS instead, possibly lowering the resolution to 512x512 if possible (would then use just 2x the memory as the 1024x1024 compressed version).
An uncompressed DDS of 1024x1024 will use the same amount of memory as the compressed 4096x4096 version, which is why I would try to lower the dimensions if you go with the uncompressed option. I gave a 2048x2048 version a quick test as well, and while it did look better than the 1024x1024 version, it was still rather obvious and nowhere near the quality of the 4096x4096 version.