Unhook the battery and leave it for a while. Then hook it back up and see if THAT helps. My next step would be to try another battery.
This is a very strange issue.
Check for the remote start and then check to see if maybe the previous owner stashed the other key somewhere in the dash - so the remote starter would work. Maybe the other key is interfering somehow and maybe because of the new battery. I'm just grasping at straws now.