Did you re-initialise the unit after changing the battery ? If so, try another battery and re-init.
If you get this message only after a power-up it's probably the battery or the battery circuitry.
If you get it after it has been powered up for a while, it is probably some hardware fault.
