On the new remote hold down the “LEFT (rewind) + MENU” button. This will forcefully unpair the remote you no longer have.

Now hold down “RIGHT (forward) + MENU” to pair the new remote.

Source: Apple Discussions