Wireless Printer problem, without much info.

Alright, well here's the story. Someone called me up today with a problem regarding his wireless printer. This is a summary of the info I was given without any assumptions:
1.) He has two laptops that did work with this wireless printer before.
2.) After one laptop was upgraded, it now fails to print, and the problem affects the other laptop as well now.
3.) The printer is an HP wireless one of some kind that connects to a router which the laptops use.
4.) He can print fine if he connects the laptop to the printer via a wire and reinstalling hp's software, but after going wireless and rebooting it doesn't work again.

From what I gather/assume I would guess that the problem lies in the IP's and is between the router and printer itself. However, as I have never setup a wireless printer (My printer being something like 5 years old which connects via a thick cable to an old family computer, since I rarely print,) I was wondering if there is something else I should be looking for and if someone could point in the direction of a manual for these things incase I simply decide to redo everything from the ground up software wise.

Any help would be greatly appreciated. My apologies for the lack of information, but the first time I will get my grubby hands on the stuff to get a look at it for myself is after the long drive tomarrow to fix it.

IPs won't be the problem if the laptops can get online wirelessly without problems and print on the wired network without problem. This means that everything has a valid IP address and can transfer data.

More likely is that some update was a Windows Firewall related issue that disabled file and printer sharing. Check that all firewalls are turned off for testing purposes. Then check to make sure file and printer sharing are enabled on all PCs.