So, I got a game going with a friend. At first we weren't connecting so we both went to double check our friend codes. Turns out they numbers had been resolved into names so we tried again. By jove, it worked!

I don't know if this is a workaround of sorts as I've not reproduced it but perhaps if you're having trouble connecting to a friend you could both try going into the Friends & Rivals screen, checking the numbers have been resolved and then trying to connect again.

I've put a poll to show success rates of this method. If it works, maybe this thread could be stickied...

Here's a better explanation of the method:

When you're trying to connect and it's not working, give it a few minutes and then cancel. Back out to the WFC menu and access your Friends and Rivals. With any luck your friend's Friend Code will have changed into their name. At this point, try to connect to a Friends Match again and, with any luck, it will work.

I hope that made a bit more sense!