Chris,
I'm running my A+ in router mode, and Bonjour services are working fine. My Macs can see my AppleTVs for AirPlay Display use, and doing a Bonjour scan of my network using Apple Remote Desktop on my main desktop shows all of my other Macs and allows me to control them.
A couple of thoughts on your situation: Are you running your A+ in AP mode? If so, can you try it in router mode? If not, have you tried connecting your A+ to your existing router using one of the LAN ports rather than the WAN port? (The latter has been suggested in other threads to address a problem specific to AP mode)