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.
