If you are using a unix system you could try dns-sd -X udp 123 456 789
If the external port result is 0 then your routers UPnP implementation doesn't work with your system. If the external port is >0 then it is unlikely your router is the problem. This is presuming you are using UPnP.
Tell me to shut up if I'm on the wrong track please.
@Duncan, everything is worth a try, even switching something in and out can sometimes magically fix this type of issue.