[edit] I guess a full restart was all that was required. Strange though, an iTunes restart did nothing.
Before you jump on me (I did a search and found nothing), let me explain the situation:
I have two Minis on the same network, one is connected via wi-fi (it's an Intel machine, if that makes a difference) and iPhone Remote works flawlessly. The other Mini (PPC — media centre) is connected via Ethernet and cannot see the iPhone Remote at all (but does see the iPhone when physically connected).
The firewall settings on both machines are the same, as are the sharing settings. The Intel machine can see the shared iTunes library of the PPC one, and vice versa. iTunes (updated today) is set to look for the remote, but does not find it.
Is this because the PPC Mini is not on wireless despite being on the same overall network? That's pretty shit if it's the case but the Apple website only states they need to be on the same network.
(Oh, and new iPhone, yay!)