I've been having this issue as well. Unfortunately, I'm just as stumped as you are. I'm using a 3DS, and I know I've configured the DNS the way IR GTS tells me to. And when I test the connection, it's always successful. However, when I try to enter the GTS in the game, this EXACT SAME MESSAGE appears.
Does anyone have a solution?