I've been around the proverbial block a few times with this one, and have eventually come across a fix that seems to work.
For those of you still getting a horrible percentage of NAT errors in Company of Heroes while playing Online, i have come across a thread online that takes a rather simple approach to fixing the error.
if i am able to, i will supply the link to the person who was kind enough to do a screen dump of all the screens you need to open to make the small but necessary change.
Basically you are adding your own pc to the services running on your network that internet users can access.. for those that do not know their own IP address, simply run the cmd prompt from the start menu and then type IPCONFIG and hit enter to get the full network details of your machine.
Thankfully i have had no NAT errors since adding this..
I hope you guys find this just as useful !
Good luck - and see you all online !