Resetting the SMC (according to the instructions above by removing the battery) did in fact work for a while, but then the service battery error came back.
A friend and I have the same problem and I noticed that we also had something else in common--our AC adaptors had fraying at the strain point where the adaptor cord meets the connector. Perhaps the fraying was causing a discharge issue?
Sure enough, once I got a new AC adaptor, the service battery message went away all on its own, and hasn't come back.