Static IP/ Strict NAT

So I setup a static ip and fowarded those ports needed to open your NAT. Normally I wouldn't because using the 'Automatic' feature never gave me problems until about two days ago when my friend and I couldn't join each others parties or connect to each others hosts. My NAT was open and so was his, but still nothing. It's funny that all of sudden we couldn't connect, because we had been doing it all week. So back to the static IP part. I can connect to everything fine. I've followed every tutorial to a T and I get this message about a strict NAT. How would I fix this? I have disabled UPnP, because supposedly thaat helps. Anything else I should try?

What brand router do you have? Then I can help.

Edit: You disabled UPnP? Enable it, it stands for Unversial Play and Plug,

Not all routers are fully compatible to give an open NAT, but the easiest thing to do is set up a static IP and put it in a demilitarized zone (DMZ). That opens up all the ports, just in case you did something wrong.spazzx625