I had this issue and did a lot of research and testing of various things (including reinstalling, power-cycling, factory resetting, etc) and read on a forum that someone had fixed the issue by rebooting their Wifi/Internet router. I was skeptical, because that should really have nothing to do with my Mac connecting to my printer and everything else was working fine with the router, no issues...but believe it or not, it worked. As soon as I rebooted my FiOS 3100 router, my Mac immediately saw the printer that it had not been able to connect to for months. So as unlikely as it sounds, give it a try. Mine is a combined Wifi and internet router, but if you have separate devices, reboot them both.
