Online play currently sucks but here are some tips to improve it while the developers are fixing it.

The best option to get online game working is to pick the pantheon or skimish mode.  If you pick those and the game doesn't start within 5 minutes, retry.

As for custom mode, here are my opinion on success rate:

1v1:  90%
2v2:  50%
3v3:  10%

Since this game is peer to peer, the more people, the harder to get a game going.  So first see if you can get a 1v1 game by hosting or joining.  If you can get 1v1 human only game, that means there's nothing wrong with your computer, router, or firewall.
To attempt 1v1, when hosting.  Hit shift-tab and click chat.  Tell people to try to join your game and post your game name.  People will tell you that they are successfully joining or failing.

Once you know 1v1 works, you can go for more players but success rate may vary.
In the beta, I had it working for 5v5 so I know it works.  It's just once you have a bad player connecting to you, then the game is ruin and you should just restart.

Good luck.