I decided to post my problem AND my solution in the same message. I had tried a lot of things and could not solve my problem until now.
My LaserJet Pro CM1415fnw (which is no longer supported by HP) is connected to my wireless network via an Arris router, and has worked flawlessly for years. Suddenly sometime in September 2015 all my Macintosh computers would give me an error "Printer not Connected" and my queue would stack up. However the printer would have no error, and is still connected to my SSID broadcast (my network name) OK.
If I turned the printer OFF and turned it back ON it would then start printing from Macs again until it went to SLEEP. Then it would repeat this behavior.
This happened on both of my Macs (which were both on the latest Yosemite OS). My two Windows 10 PCs and my Windows 7 PC had no issues - printer always showed online and always printed.
Things I tried (skip this if you don't care):
1) I tried downloading a new driver for the Mac. But I could not install it because... You guessed it... It could not find a printer online to connect to. If I rebooted the printer it would not stay online long enough for the wizard to finish connecting to it. Ultimately I think I managed to successfully update the driver but it did nothing to fix the problem.
2) I went to my Windows computer and updated my printer's Firmware loosely using this guide (as it wasn't EXACT but I fished around to find the Firmware updater):
At least in that I went into my Arris router via a web browser and set up a single fixed IP to be my printer, and then I set the printer's TCP/IP to the same fixed IP number, so that it was never reassigned. In theory that accomplishes the what the thread says was a common problem. But it did NOT fix my problem.
4) I upgraded one of my Macs to El Capitan. It did NOT fix my problem.
1) Apple Menu > System Preferences > Printers & Scanners
2) I clicked the " - " button to remove the printer that always showed offline (HP LaserJet CM1415fnw)
3) I clicked the " + " button to add a new printer
4) I clicked the IP button to add an IP printer (instead of using the default button)
5) I entered the IP number that I had manually set on the printer.
6) I left Protocol at "Line Printer Daemon - LPD"
7) After it looked up my printer I added it.
DONE! Now it prints fine and dandy from my Mac again.
You will need to make sure that the IP number for the printer never gets reassigned automatically by your DHCP, otherwise you'll have to re-add that IP using the above steps. With my printer (may be different with other printers) I tapped its Settings icon, then chose the down arrow until I found Network Setup, then chose TCP/IP Config, then chose Manual, and I entered the IP number I wanted for my printer. (I left the rest of the settings such as the Subnet as what it defaulted to.)
But your router has to agree that this is the right IP number too. Most routers can be accessed via your browser by typing in 192.168.0.1 with the login of "admin" and no password (unless you changed it). Linksys routers may use 192.168.1.1 with no login and the password is "admin" (the other way around). Netgear routers may use 192.168.0.1 with a login of "admin" and a password of "password."
From there, you have to figure out your best solution for telling your router what you want your printer's IP to be and keep it that way. Some threads will tell you to change the IP range that is automatically assigned and set up the printer's IP to be outside that range. That is not what I did. My Arris router, I clicked on LAN Setup tab > Client List button and in the "Reserved IP Client List" section of the panel I clicked "Add" and added the IP number I wanted for my printer there. (It happened to be the same one that was automatically assigned.) It's the same one that I set up in my manual setting in the printer's TCP/IP, and the same one that I set up in the Mac's "Add an IP printer" area.
A solution I found later that I had not yet tried (in case you want to try it):
Set up e-printing. This actually sets it up so that your computer "emails" your print job to the printer, which gets its own email address. This is a circumvention, not a fix, but who cares, if it works. My solution is sort of a circumvention also, just not as big of one.) I have no idea if this would've worked for me... Maybe it would've been easier, maybe not. You can try it out.