well from what you describe, the problem seems to be in the valet button. Hopefully it is just a loose wire or it got kicked off.
Since your old remote worked, the brain must have power and be somewhat functional.. The only other thing I can think of to tell you without seeing it is to play with that button....
try to push and hold it in before you insert the key, after, ignition at different positions etc.. Also 5 seconds is just an estimate. Make sure you hold that thing down for long enough.
Also, you said the old remote went bad... can you replace the battery? How can you be sure the remote died and not the alarm brain?
I dunno man, sorry I couldnt help.

if you decide to take it in somewhere take it to an alarm installer, they may be cheaper than a dealer, maybe not.