Bonjour has some serious issues on Yosemite. It is really frustrating as it is quite random. Restarting your Mac (and the printer) may solve the issue for a while, so you can do your work at least. It is discussed widely. Very often I cannot see other Macs on my network (while I can connect to them using IP address) and I cannot see Bonjour users on Messages (iChat worked perfectly).
I may suggest a series of commands to run on the terminal, if you are comfortable with that (and are the administrator of the computer, you'll have to enter your password):
sudo launchctl unload -w /System/Library/LaunchDaemons/com.apple.discoveryd.plist
sudo launchctl unload -w /System/Library/LaunchDaemons/com.apple.discoveryd_helper.plist
sudo ifconfig en0 down
sudo ifconfig en0 up
sudo launchctl load -w /System/Library/LaunchDaemons/com.apple.discoveryd.plist
sudo launchctl load -w /System/Library/LaunchDaemons/com.apple.discoveryd_helper.plist
en0 represents your network interface
It might be en1 - you can see what you should use by running on the terminal:
networksetup -listallhardwareports
It should be pretty self-explanatory.
Now, this is not a permanent solution. It is much like restarting your computer (which might actually be faster if you are slow with the terminal). But I've been at points where I did not want to interrupt my work and just issued the commands above and I could ("magically") see Shared Computers on my Finder sidebar and Bonjour users on Messages.app.
It might be my router, I don't know - and I shouldn't care. It worked great before - with Yosemite it doesn't.
I also wanted to point out, that there is no way that you can uninstall Bonjour, using a product like CleanMyMac. I've actually used it for years and have never had any issues like that. And actually I think it's a quite good product - I clean up caches, uninstall apps without having leftovers and occasionally manage extensions that may be installed without me knowing. It does not delete system files or messes up with services in any way.
Now, I don't know why John is so much against CleanMyMac. There are others like MacKeeper that use very aggressive advertising and actually are crap apps. Generalizing that any clean-up utility is "ill-conceived" is close to paranoid. Sorry, but I like that 5GB of cache created from internet surfing or logs back when I got a 128GB drive. And I don't like leftovers from apps that I just wanted to try out (OS X does not help at all on that). Having a nice interface for it and not having to dig around my Library folder is more user friendly. And no, I am not affiliated in any way with MacPaw.