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.