You must have a non-shared IP address for the duration of the game. This depends on your provider and there is little you can do if you only get shared IP addresses. See the "legacy" solution below for a possible workaround.
If you use a hardware firewall you have to clear port 45000 for inbound and outbound traffic. See your firewall's manual for attaining knowledge on how to do this. Software firewalls usually ask for permission of internet access for PGIE. If you permit this it will work.
If you use a router you have to route inbound traffic on port 45000 to your local IP address. If you seem to have this problem -and this is the most common problem in online gaming- here are some ideas of what you can try:
First, attempt both directions of connecting: Retrieve your IP address from http://www.whatismyip.com/ (Note that 'ipconfig' does not give your WAN address if you are behind a router.) Exchange IP addresses through instant messaging and try connecting to the other player. If it does not work have him try to connect to you.
Another solution worth a try: Use the connection server of Killerbeesoftware instead of directly connecting through IP addresses. (If this works your router was not the problem.)
The "clean" solution: You configure your router to forward Port 45000 to your local IP address. Then you retrieve your external IP address from the router's configuration page (or from http://www.whatismyip.com) and give it to the other player. You can't get the external IP address with 'ipconfig' if you are behind a router.
The "brute" hardware solution: You bypass your router by disconnecting it and connecting your computer directly to your modem (cable, DSL, ISDN or whatever type of internet access you use). Afterwards, you need to have your internet provider's access data at hand in order to establish a direct internet connection.
The "fairly clean" solution: Some routers allow to configure a pass-through of PPPoE connections. This has the same effect as the "brute" hardware solution but you save yourself the rewiring of your hardware.
The "quick and dirty" solution: You open your router for all ports and forward them to all local addresses. Many configuration pages of routers offer this as a 1-click-solution. (Note that you must not let any other user hook up to your local network while you're playing then!)
The "legacy" solution: Dig out your old analogue modem (many computers still have a built-in one) and hook up to a call-by-call internet service provider. PGIE works well with low band-width. (Make sure you don't get anybody mad at you for blocking the telephone line while you are playing, and try not to have your system download tons of updates while you are connected this way!)
