Have either of you tried playing with anyone else?
Have you tried joining in the lobby, in addition to invitation?
If the multiplayer setting is on invite only, try switching it to friends only or public.
Try going into Arena mode, create an arena, open the Connectivity menu and check the settings, then exit to the main menu and try joining in the lobby. Alternately, create a multiplayer game lobby, exit and try joining.
Can you also try switching between wifi and wired, if available, or testing with a mobile phone's wifi hotspot feature, or other available network?
