Two things: 1. are your ports forwarded? and 2. do you have UPnP enabled? If your ports are forwarded and you have UPnP enabled, uncheck the "Disable UPnP" box from the Network tab in the Options menu if it's checked. If your ports are forwarded and you're already not using UPnP, first try enabling UPnP and if that doesn't work, unforward your ports and try again with UPnP.
I'm basically throwing around some troubleshooting ideas. If none of that works then I have no idea what the problem is. I'm just guessing here.