I didn't realize the procedure had changed for the newer models... good to know. It's interesting that you really have to kill the battery to get it to calibrate on those.
How old is your battery? Hopefully a calibration will help, but it does have a finite lifespan. After you calibrate and recharge, open Apple Menu -> About This Mac -> More info and then click on the power entry. You'll see a max charge capacity number. That number is in mAh. You can find the original rating of your battery (probably about 4000?) online and see what the current capacity is by dividing the current number by the original number....