Is this a shared printer, attached to another PC or a network printer on a print server?
If a Print Server, what is the make and model? If a network printer, what make and model?
Are you running Vista or XP?
Try opening OneCare, click Change Settings, and on the Firewall tab, configure network - make sure it is shown to be "home or work." On the advanced button, ports and protocols tab, place a check mayk next to "file and printer sharing local subnet" and "file and printer sharing subnet and Internet."
-steve