What's the printer model? If it has WiFi or ethernet it would make it a lot easier to set up instead of having a PC share it, which I never found reliable.
Sounds a stupid question, but is the printer fully online when you attempt this? Often on the first time you add one, it wants it to be fully online, rather than in sleep state, despite that you can see it on the network. "Seeing" it on the network, does not necessarily mean it is online and can be windows "knowing" about it, but it's not really online.
Otherwise, have you checked you have all the windows file and printer sharing stuff turned on? There's a menu option somewhere in windows where you can click a toggle to turn that stuff on. I can't get it to it now on my work machine as it's all different as locked down via corporate policy.
It's an old Brother Mono laser printer with mega cheap toner so it works great. It would just be really handy if I could print from my laptop.
I've tried adding it just after printing to it from the desktop so I assume it's not sleeping. All sharing settings I can find are on.
Is it connected via USB? Which Windows version is the host using as well as the others? You may need to go to control panel -> network and sharing -> advanced sharing settings -> all networks and turn off password protected sharing.