I see that jbgordon got his problem solved by getting a new battery (congrats), but I thought I would respond anyway because this exact same situation happened to me, and I learned the hard way how not to treat a lithium ion laptop battery.
Just like jbgordon, I left my laptop plugged in almost constantly. In fact, I only had 17 load cycles after 12 months of owning the laptop, if you can believe that.
Then one night, during a lightening storm, I decided to unplug my magsafe adapter just to be extra safe and protect against the possibility of a surge (even though I have the adapter plugged into a surge protector). I got down to about 45% and the laptop shut off. It continued to do this any time I got to around 40%.
I can't remember exactly what my battery health was at the time, but I do remember that it wasn't awful (I think it was above 80% reported in coconutbattery).
After some online research I learned that my leaving the laptop connected to AC power most of the time caused this problem. It seems that the problem is two-fold from what I understand :
First, when the battery is not discharged and charged relatively frequently, some of the energy becomes effectively unusable. So you end up with a battery that reports a certain percentage of health, but in fact can only provide a fraction of that percentage of power in real world use. (some of the power gets "locked" in the battery)
The second problem is that, if you're like me and left it plugged in all the time, you probably never (or rarely) calibrated the battery. The "fuel gauge" on these batteries is actually controlled by a chip in the battery itself, which reports the data to the computer. But if the battery is not calibrated regularly then the gauge will have an inaccurate picture of how much total energy the battery can provide.
So these two issues combine to create a situation where a battery reports a certain level of health, but can't actually provide that amount of energy (so the battery shuts off before it reports that it's low) and you can't calibrate it to correct the problem because, of course, it's impossible to take it down to zero health. (calibrating the battery by letting it sleep/power-off for 5 hours after it shut off at 40% doesn't work).
Basically once a battery gets to this level it's ruined. Luckily I was still within my warranty (barely. only by a couple days) so Apple sent me a new battery.
So the moral of the story is : Don't leave a laptop plugged in all the time.
jbgordon's battery (or mine) wasn't defective, it was just the constant AC power that killed it. So if you get a new battery, and do the same thing, it will be ruined shortly as well.
I recommend using the laptop on battery power (taking it down to around 30-40%, then charging it back up) at least twice a month. Apple recommends that you calibrate your battery once every two months, but if you leave it plugged in often, to calibrate it once a month. I do the latter.
Here is the calibration process :
http://support.apple.com/kb/HT1490
EDIT :
Here are links to the articles where I got most of my information
http://www.apple.com/batteries/notebooks.html
http://www.batteryuniversity.com/parttwo-34.htm
