Reset Maintenance Count

Reset the maintenance count on an HP LaserJet 4000, 4050, 4100, 5000

Turn the printer off.
Hold down the [Item-] and [Value-] keys.
Turn the printer on.
Wait for RESET MAINTENANCE COUNT to be displayed and then release both keys

If that doesn’t work, then go into service mode to reset it.  Note that resetting it simply resets the count so the message goes away.. you still have to perform the maint if it’s really necessary.