There are quite a few comments/suggestions, that if you receive this message, then your battery is, as it says, about to give up.
In this thread, there are several ways suggested (I was one) as to how to get the OS to say fully charged. In most cases, this is temporary, although some seem to have been succesful.
As I understand, even now still in the rumour stage, it occurs on just a few computer motherboards with a particularr Intel chip? (Acer 700 series seems to be one such).
But. One thing of which I can assure most users. It is not, in the initial stages, a battery problem!
I was lucky enough to have access to batteries, when this problem occurred. All, of three, new batteries, gave the same message after a short useage.
I believe that the original (cheaper!) batteries, can, with undercharging, eventually change their "memory" and adopt a new maximum figure, beteen 80 to 90%. This does mean a spoiled battery in the long run, when the situation become irreversible.. In the same context, I have read that more modern Nicads do not have this memory problem.
Most computers exhibiting this symptom are probably, by now, out of guarantee unfortunately.
The only way to cope with the problem, if you have gone to the extent of purchasing a new battery, is, as with all rechageables, to, from time to time, allow the laptop to discharge the battery to varying levels - even completely if you are able (Not too easy with a laptop, it always has a fairly high residue.)
Several methods of achieving this are in this thread.