iPhone/iPad unable to see iMac/Apple TV until router reboot (affects AirPlay, Remote app, Wi-Fi sync)
Sounds like a router problem.  Bonjour/Zeroconf uses multicast to reach all hosts on the network - if the router treats these incorrectly you have the problem.

If the rest of the network works correctly, then the simplest thing might simply be to replace the master router of your network with an Apple router (they tend to work well with Apple units) and set the current router to be just the internet uplink.