I am assuming your remote start was installed after market.
If this is the case it sounds like the immobilizer module for the theft deterrent either needs reset or replaced. If you take apart the under side of the dash below the steering wheel you are looking for a small 2"by 2" module. By finding the specific model number of the immobilizer you will be able to research the reset instructions. Normally you press and hold the reset button until the LED display blinks, start the car and it should reset to the pass lock.
If this does not work, disconnect it and replace it.
The passlock will reset within 15-20 minutes and should start. If it does not restart, try remote start and hit the brake to kill it, then wait it out.
Sometimes these immobilizers go bad when you replace the battery.