Hmm. Actually, I wonder if you might accidentally be doing a dual NAT. Check to see what your router thinks its external IP address is. It might be that your ISP's modem is doing it, and then your router is doing it again, which would break things (even if you got a new router).

Anyway, if your router thinks its external IP starts with 10. or 192.168. or 172.16. thru 172.31., then this is your problem.

I do wonder why MS calls out those routers in particular as being incompatible. Surely there are many more that didn't support UPNP.