Its kind of irritating to see players with the same issue scattered around the forums helplessly. Why not gather everyone under one thread so the admins might have an easier time addressing this issue? (if they plan to, that is...)
Apparently the issue is even after the usual solutions (portforward, disabling firewalls etc), a portion of the players are unable to connect to others, or the others are unable to connect to you. We cannot connect to others probably because Demigod works in a way that we firstly try to connect to the host/host connects to us. If the host is unable to connect to us, the rest of the players in the lobby will appear to us as 'Waiting to connect to xxxx', with the host 'Attempting to connect to xxxx'. If the host is unable to connect to you, then you will be stuck with connecting to the host and no one else gets to connect to you. (just what I observed)
IMO, this IS a problem on our end. The host is able to connect to others, but not us. It lead me to think ports are not properly opened or something is blocking the connection on my end, but seeing as others who have the exact same problem, I was thinking Stardock should at least attempt to help us by at least replying to our help threads.
How the problem looks like:

Well, McShane87 (sorry to use your name here if you see this) is the host of this custom game. I can connect to him as you can see me as aqualeris, but he cannot connect to me, as seen by the 'Attempting to connect'. Because the host cannot connect to me, the others are queued behind him. As long as I don't get past the host, the rest will forever be unable to connect to me, thus shown by 'Waiting to connect'. Host always has the top priority to connect to a player. (this is purely based on my observation after testing this bug out for many times. Someone correct me if I am wrong. The connectivity in Demigod is highly complex so I might get this wrong)
Soooooooooo....
I'll make things even easier to the admins. All players with the same issue, please gather under this thread and sign!
Signed, aqualeris.
Cheers people!