Before you go to all the trouble, get hold of a battery that you absolutely know is a good one - ie you have seen it start another car.
The NATS system very very rarely just stops working.
As said above, you need to check for any error codes. There is a guide in the Guides section on how to do a "pedal dance" to get the codes up by using the indicator flash sequence.
If it comes up clear, it is highly unlikely that it's a NATS issue.
In fact, IIRC if the does not recognise your key, it wouldn't even attempt to start the car - ie no "chugging" as you described it. Does the key remote unlock the doors?
I am leaning towards a battery issue still.