We got one game in last night, and it worked without a problem. Very strange.
Since this is happening at the point where I need to connect with my friend, I have to think that the problem has to do with the part of the game that connects players. The main server might not be the issue.