I've found that Remote only connects well if the wireless is doing the right thing. A lot of wi-fi routers don't actually handle broadcast traffic (which is what Bonjour uses to find services) very well. Apple's ones do...

Once the Remote is linked with an iTunes instance, I think it behaves a little better, but that initial negotiation depends on good broadcast packet behaviour.