I paired a remote on the MBP and another one on a mac mini using the menu + fastforward method.

rather odd problem you had there.

Using the new core duo mac mini I found where some people may also run into a potential problem. It didn't seem to want to pair the device using either key combination. After trying them both, all of a sudden it appeared that the remote wouldn't work. I looked in system prefs to check that the remote sensor was on, it was, and it claimed that the remote was not paired. I then realised that I wasn't logged in as an administrator. Once I had logged in as an administrator, the remote still didn't work, but now system prefs claimed that a remote WAS paired with the computer. Unpairing the remote then got the remote to work once again.

Moral of the story - when pairing a remote, make sure you're logged in as an administrator!