Have you checked your journal I remember I had one of the HM dungeons given by that npc unlocked and didn't know it until I checked my journal