Well my firewall is off but I do have a router.
I read the topic with the router problems but the problem is I dont know how to forward ports or anything like that.
Though a friend of mine might help me soon with it.

Thank you for clearing that QOTA thing up.
So basically the one who does not have QOTA shoud always host the game?
Or is there a way that I can host a none QOTA game as well with Gold Edition?

Also, do you know how it is possible that when my friends selects 'LAN' he gets a message stating he should select a server first?
When I select 'LAN' I get a new screen and not an error message.