I bought the game yesterday to play with some friends, fully patched it and got the CD keys. But for whatever reason can't see when my friend makes a game and he can't see/join mine (With unlocked spaces). I'm probably missing something obvious but its frustrating, also we can see each other in the chat lobby online, we just can't get into a game lobby.

Look here - http://www.gog.com/forum/sacrifice/cannot_connect_to_online_multiplayer

This seems to be a different issue, I can connect to the server just fine and am able to see the people in chat lobbies, I just can't see or join games. And I have changed the CD key in the options menu.

You may need the following ports forwarded in order to play:
2302-2400 UDP
6500 UDP
6073 UDP/TCP