I finally figured out my NAT issues. I'm posting this because so many games are affected by NAT / router issues. The main NAT problem I've been having is PSN's new party chat feature. Because the chat works by having individuals self host the VOIP on their own systems, many people will experience NAT errors because of their routers.
This is not a step by step guide, but instead its a list for future reference for anyone that is having NAT issues and the steps I performed to fix them on my ne