I searched for a similar thread and couldn't find one exactly like this.
My NAT settings are at Moderate and I was wondering how exactly I could fix this, I am playing Crysis 2 on PC.

Are you behind a router, or is your PC firewalled? Try enabling uPnP on your router if it's not already enabled. If that doesn't work, you may have to find out what ports MP uses and forward those to your PC, or add exception rules for them on your PC firewall.

I play on xbox, so I'm not 100% sure on the details of PC gaming. Isn't the PC version run on dedicated servers, though? Why is having moderate NAT an issue?

Yeah uPnP is enabled and I just like to have an open NAT because it doesn't take forever to find a server through the quick match.
The dedicated servers are horrible right now IMO, I got to join a game that says 8/16 and it will say it is full.

Might just need to foward some ports to your PC then. I'm not sure what Crysis 2 uses, try a google search. I did a quick search myself, but couldn't find a definitive answer.....

Yeah probably the easiest way

The NAT status is completely worthless and inaccurate. I run without NAT of any type (I have my own tiny subnet), yet the game says "moderate", turn off the firewall and it makes no difference.

Very occasionally it changes to "unknown" or "strict" for no reason at all.