Wireless router that supports Bonjour between wire- and wireless- connected machines

It looks like the router isn't handling multicast (which is what Bonjour uses) correctly. There's a possible fix mentioned here although it might not work with your particular modem.

Anyway, multicast bridging is the feature you want, although it's hard to determine if a router supports it without actually testing it. If you are happy running separate networks for wired and wireless, one option is buying a router with OpenWRT support, then running Avahi as a mDNS reflector between them.

I can report that my Linksys WRT54G without custom (OpenWRT) firmware supports the bridged multi-cast traffic just fine. Wifi printing to a wired HP printer with Bonjour/Zeroconf works. However in my case, the firmware on the HP 2600n had to be patch to the latest version to get this working correctly, so it might not be your router at fault.