If you go to the Security System Preferences panel, you'll find a Pair/Unpair button. Clicking on Pair brings up a message instructing you to press and hold the Menu and Next buttons on the remote until a "paired" icon appears.
I tried this several times with no luck. Finally, I found that you have to be running an admin account for this to work -- there is no indication that you can't pair from a non-administrator account. As a matter of fact, the panel is disabled until you click the lock and enter an admin account and password. But even after unlocking, you still can't pair from a standard account.
So if you have trouble pairing a new remote, make sure you log into an admin account first.

