Has anyone heard of this before?

I had a car starter installed in my wife's 2001 EL. They used the valet key to use as the "skim" key so the remote starter would work (I don't know if this detail is important to answer my question.)

In the process, they disconnected the battery, and therefore the security system enaged, and the display shows "CODE".

We've inputed the code on the security card we got with the car manual, but it doesn't work. (We know the code is correct, because a couple of years ago it did work.)

Anyone have any suggestions?