I'll have to retry this to get the error number, but a similar thing happens to me when I try to connect with one person. It's strange, I can get into some friends' towns just find, but there's one that I never can. I see him on the list and I try to connect, but it never works. Same when he tries to get into my town. The thing is, the same thing happens with MKDS. We see each other connect and search, but we just can't make that connection to start playing. Furthermore, we've been to each other's houses and connection via WiFi there, so we know it's not out DS's having problems communicating with each other.
My guess is that there's something up between our routers. We're fine otherwise, but when connecting to each other it fails. We basically have the same router as well, same company and very similar model (which I've forgotten right now =o). Very strange indeed!