This just started happening to me too. I also have a 2009 Macbook pro 13-inch.
I've read somewhere that this just means that the battery dropped below a certain % of max capacity. Via coconut battery my current capacity is 78% but it was at 73% earlier today (lowest it has ever been). Does anyone have anymore insight on this? Is my battery failing or just old?
I'm using the computer right now on battery and have been for the last couple hours and it seems to be running fine. I get ~3.5hrs when I'm trying.
Edit: Thank you el-john-o. I think it was from you that I read about the 80% spec thing
I believe the 09 MBP uses Li-Ion batteries. Those will gradually lose a charge over time (what you are experiencing) then decline a little sharper, then fail altogether (where you might get 10 minutes of battery life). It's just a fact of life, even the best rechargeable battery packs fail. If it's time to upgrade, replace the machine. If it does everything you need it to do, save your money and buy a new battery. It's really not super difficult, but, Apple is reasonable as far as pricing to have them do it. (Though, again, it's a piece of cake).
LiPo batteries, like on the newer MBP's, will not have as much of a gradual drop. There will be some, but then they will suddenly fail. I suspect a lot of forum posts in a year or two with people complaining about an 'overnight' change in battery performance. It's actually an improvement, because during the 'gradual failure' stage of a Li Ion battery, a LiPo battery is still maintaining most of it's charge. At the time the Li Ion battery fails, the LiPo will suddenly fail as well! (In terms of charge cycles and such). Unless Apple has some sort of special LiPo cells, this is how LiPo batteries typically behave.
In either case, it doesn't hurt anything to use your laptop with a failing battery. It simply means you cannot rely on the battery to hold a charge. I also wouldn't be too alarmed if the battery reporting was way off (showing 1 hour until empty, then force shut down 10 minutes later, etc.). It's nice to replace it so you can go back to being portable, but I've got an older Windoze laptop that I use occasionally that has no battery, most of the time Windows can't even recognize the battery as in there, and it will just 'shut off' (not shut down, just 'die') within 2 or 3 minutes of being unplugged. It's shot. Been that way for a while too. It's sits on a desk in my bedroom though and my wife uses it to check her facebook, it's basically a desktop now (those things shut off when you unplug them too!

). If it mattered I'd replace the battery, but, it really doesn't in this case. If my MacBook Pro started doing that, that'd be different, I use it 'unplugged' all the time and would definitely want to replace the battery.
Again, the 'battery service needed' has a lot more to do with staying within Apple's specs. Not every Mac user is a computer whiz. Some may have no IDEA that batteries fail over time. That little reminder should get them to have their laptops looked at in plenty of time, before the battery fails completely and they are left totally surprised by the fact that they can't unplug their laptop anymore!
For the record, there's not much you can do to fix an old battery, but there are a few things you can do to keep it lasting longer. For one, , follow Apples instructions on 'calibrating' the battery about once a month. New MBP's don't need to be calibrated when new, that's true, but they should still be calibrated monthly or so. This is true whether it's a road warrior, or whether it's plugged in 24/7. Newer batteries are less susceptible to 'memory' (where they CAN hold more of a charge but due to poor charging habits are 'stuck' using only a portion of their capacity), but the electrons need to move. Failing to discharge and recharge the battery occasionally will accelerate wear. Conversely, it's best to leave the battery with plenty of charge if at all possible. Though the electrons do need to move OCCASIONALLY, the battery will last the longest if the only times you discharge the battery completely are your occasional calibration stints. I know that all seems odd, but it's true!
-John