12 V relay instead of 9 V?
According to the data sheet, the pick-up voltage is 75% of nominal, so if you put just over 9V in then it should just switch on. 

That said, there doesn't seem to be any reason to change the relays for ones which only-just work at the given voltage where the same range has 9V relays ( which should work for 75% to 130% of 9V ). The 9V voltage is the coil voltage, not the what the contacts are rated to, so choosing a relay with a higher coil voltage will make the car less reliable - at best, it will stop working immediately the battery dips below 9V.

Given the relays click when operated, indicating that they are mechanically sound, you should be worrying more about whether the motor is working rather than the relays. ( it is possible that a contact has failed in the relay, so a relay which clicks might have failed, but usually contacts fail by getting stuck in one position, so if you hear them click it's more likely that it's the motor ). Disconnect the motor and try it directly connected to the battery.