Read the FAQ - you need to open some ports in your firewall to connect to ICO.
If you are having issue connecting, try turning off your firewall for a second and see what happens. If you get the issue, it is something else, if you don't get it, then the issue is your end.
I suggest opening your config.setting file (for me (Vista) it is found at C:\Users\XXX\AppData\Local\Ironclad Games\Sins of a Solar Empire\Setting)
Open the ports it mentions and if you want to host, ensure you are port forwarding 6112 to your game PC from your router.
GameHostPort 6112
GameBroadcastPort 6000 (this could be some other port such as 6001)
IcoServerPort 7000
I hope I got that right and that it works. The reason why this is different and people think it doesn't work (and it does really - I only have issues when my PC 192.168.1.X address changes, or a alter modem/router settings) is that this game uses P2P rather then traditional client/server (with the exception of the ICO lobby part - since that is like IRC).
Good luck