Have either of you tried playing with anyone else?
Are you shutting down all non-essential programs before starting the game, especially anti-virus and anything network related (utility or monitoring programs, etc)?
Have you tried hosting/joining an Arena match?
Did you try reinstalling?
With the Steam version there is a way to effectively reinstall the game without having to redownload it.
Right click on the game in the library and select 'Backup Game Files...'. When that is done, right click again and 'Delete Local Content...', then in Windows Explorer, make sure the install folder has either been removed or is empty (before deleting, right click, select Properties, switch to the Local Files tab and select 'Browse Local Files...'), then restore the game backup.
