It should also activate a big red sign in the controls that means: "The new key will be usable in 3 hours"; so if you actually didn't changed the keys, something is wrong.
I know the GM Passlock II system works this way - not only do you have to wait, but you have to put the car in 'run' a few times during specific times during the waiting process.