Typically this is due to "lockup" of the WCM/SKREEM (wireless control module), There is a TSB for this.
The easy way to tell if that IS the problem is to see if the keyless entry is also not functioning (If it has keyless) as when the WCM goes non responsive, the keyless entry will also quit.
Pulling the IOD fuse (number 11 under hood IIRC) for at least 10 seconds will clear the WCM and verify the problem if it starts after this (No need to discon the battery)
What causes this is static discharge from the person thru the key, it locks up the module and you are done.
The module will have to be replaced with the updated one to fix it.

Reference TSB 08-007-08


The keys have NOTHING to do with this as even with a bad or incorrect key it will still start and die 3 times before security lockout will prevent cranking


Rick