Just posting this here for easy reference if required later.
If you are playing with someone who is constantly getting the NAT negotiation error, when trying to connect to a multiplayer game, you can use Hamachi as a workaround for this. You need to use an old version of it to work though, which I’ve linked below:
http://www.filehippo.com/download_hamachi/2114/
Hamachi basically creates a virtual LAN between you and anyone in your hamachi channel. Our channel is xdcrs, with the password xdcrs, although we may be approaching the limit of users in it. Anyway, you’ll need this for any games versus Paddy atm, and potentially others. The threads here to save me having to google the hamachi version every time we need to use it in future.