New local printer on computerviewable but unaccessable by network users

I replaced 1 pc and 1 printer on our network. The pc, like the original, is connected to the network via wireless. The local PC can print no problem, but any other PC is unable to print to that printer, even though it shows up in the “add printer” options for network printers. I tried every combination of new and old printer and computer to no avail. When you go to add it, it says that the printer is unavailable or the name was possibly misspelled. Have tried new cables, wireless cards, OS upgrades, drivers thus far. Any suggestions?