I have noticed that after starting the game and logging into the internet sessions, I can get into a game without a problem, usually within a minute.
HOWEVER, after the game is over, I must restart Demigod entirely or else I can't play a second game. The game keeps finding matches but, fails on actually connecting. It may be something to do with a port not closing properly after the match. This occurs with both skirmish and pantheon games for sure. I'm fairly certain it happens with Custom matches as well.