Actually, one of the links at the side of this page had the exact problem I'm having. Seeing as how a lost remote is still a paired remote, you can't pair the new remote until the old remote is unpaired. Fortunately, you can use ANY remote to unpair--just hold down the "LEFT (rewind) + MENU" buttons to unpair the old remote. Once you see that this step has been completed, you can simply use the new remote to pair with the AppleTV by holding down "RIGHT (forward) + MENU" to pair the remote as per the instructions on Apple's help page. Hope that helps for those like me who lost their old remote & couldn't understand why the new one didn't want to pair. When the old remote is still paired, there is no message when you try to pair another remote, though there probably should be. 😁