Either the toner is defective (return for replacement) or the sensor in the printer was broken before/when it was put in.
Upon replacing the black high-capacity toner cartridge (106R01597) we still have the message "insert black cartridge" appearing on our printer. I have made sure the toner is loose inside the cartridge, tried turning the printer off & on, installing the cartridge several times, etc. Nothing is solving the problem. Yes, it is a genuine Xerox toner cartridge.