I recently changed ISPs and they also sold me a new router of a brand (AVM) which is generally considered to be one of the better SOHO router manufacturers over here.
Unfortunately, this device takes a little too long to setup the firewall rules via UPnP (when requested by MG), so when I start hosting a MegaGlest game the first attempt to publish the game fails with the error message about failure to connect to my computer and incorrect firewall setup. When I just switch on the option to publish to the masterserver again, it succeeds. I assume that's because at this point the firewall rules are already setup so the inbound test connection works well and the new UPnP request to set up these rules is not problematic since it doesn't effectively change anything.
To sum it up, the client side (or is this server side - I don't remember how it works exactly...) timeout for the check whether publishing to the master server worked out should be extended by ~5 seconds if UPnP configration is being used (or in general).