How many pages were printed between the replacement of the cartridge and the replace toner message?
There is a firmware glitch some machine would experience where the page count would increment exponentially, so for example for every 10 pages printed the page count would increment hundreds or sometimes even thousands of pages. This would cause the toner counter to expire even though there is plenty of actual toner left.
If this was the issue you were experiencing (only getting a few pages before "toner low" came back), the firmware update you performed likely resolved the issue, however you may need another new cartridge to reset the counter. Once the CRUM chip on the toner cartridge has been written as end of life, it will not reset even after the firmware update.
Honestly, it sounds like it might be the toner cartridge and not the device. Call product support at 1-800-835-6100 Option's 1, 1 and provide them with device serial number and describe the problem. They will most likely concur with my diagnosis - that the toner is a dud...
I have a xerox phaser 4510 that indicates low toner. replaceda new toner and after 3 days it is saying toner low. updated the firmware to no avail. now it is saying please replace cartridge Please any input or advice on how to fix this issue.