The remote start probably has a hidden key by the ignition switch which now will have to be re-programmed also, I think you can do that easily having 1 key already programmed, you just put the good key in ignition, turn on-off and quickly put the hidden key in and turn it on, hidden key might be nothing but the blade though, best buy should do this part for free, the AC must be a separate problem because the key has nothing to do with it except to start the engine to run the AC, the dealer is responsible for that