I couldn't believe it, but I've trashed machines for this issue. It never occurred to me to actually LOOK at the toner chip connections on the frame, and this seemed to be the issue. I found the top TWO (of the three) wire connections, that touch the chip on the toner cartridge, bent DOWN... so they weren't touching the chip. I found this on at least two machines in my shop. Bent them back up, and away the machines went. This was simply something I had overlooked, as I don't know why this seemed to happen on only the Black cartridge.

Hope this helps someone!