Hello whiskeyfrank,
If after replacing the toner the message is not clearing it must be a hardware issue, I would suggest that you call the support department to schedule an onsite visit at 1-800-821-2797 or 1-800-835-6100.
I have a workcentre 6515 and just replaced the cyan toner, the notifications still say it's still low on toner. The toner is the same code as the last and is genuine Xerox. I have tried taking them all out and that's not worked. Any idea what the problem is?