A thing that may work
System > Admin menu > OK > Maintenance > OK > Toner Refresh > OK
Select the Black toner cart OK > Yes > OK
First thing, remove the toner, reboot the device with out the toner. When the device is loaded and is asking for you to insert the cartridge, insert it. Sometimes this will work.
I forget the terminolgy that is used, but if you call Xerox and ask them how to re-initialize the cartridge settings to clear the message. You might have to talk to a lvl 2 Xerox tech to get to the right options.
I just purchased a black Cartridge from a dealer last friday Oct23...Today Oct 30 it says replace black cartridge. I took it off and shook it and placed it back..however it still said the same thing. I called Canada Computers to complain and they told me to call Xerox...so here I am asking for your assistance