Refer to this:
http://support.apple.com/kb/TS1453
It's important that the router's firewall allow the appropriate ports to be open, as well; in my D-Link DIR-655, there's a port forwarding page where specific apps/ports can be allowed. I added UDP 5353 for the Apple TV (for which I have assigned an IP rather than have it dynamically assigned) and the problem appears to be solved. If this ends up not being a solution, I'll report back.
BTW, my setup was slightly more complicated than "normal," as I have all of my media content residing on a NAS. Didn't tweak any of the router settings for the NAS.