Nat negotiation being in M2TW when you try to connect?
Reliability online was one of the weakest parts of M2TW unfortunately, I don't know of any particular tricks to improve things - so just keep trying. Lots of rude things have been said about gamespy.
It could be worth searching the forums in case anyone had any breakthroughs on connecting but as I say, can't recall anything.
I hope you manage to get on and have some good games to make all this worthwhile. Steam (or something else) can be quite handy to find people you know and ask them for a game - I'd be happy to try if I happen to be about, if I can remember passwords and connect etc, I haven't tried in a while.
edit: there are apparently some ports that, if you can, opening up might help
http://forums.totalwar.com/showthread.php/23618-NAT-NEGOTIATION-FAILED!!!-please-help[This message has been edited by SwampRat (edited 10-19-2013 @ 08:00 AM).]