I actually did that, but it tells me to go into the ATV's settings and select remote control. I can't do that without the original remote.
Add: Basically, the original was paired and it seems the only way to do this is to get another original and hold down the FF and Menu key. I would like to avoid this if at all possible.