[thstone]

I agree with Timco - sounds like the immobilizer isn't working properly. It should recognize the signal from the transmitter in the key fob and allow the door locks and starter to engage. A common cause is water getting under the drivers seat and shorting out the immobilizer.

If everything is dry, I'd disconnect the new battery, wait a few mins, and reconnect to see if things reset on their own.