This usually indicates that one of the cells in the pack is bad, and replacing the whole pack is usually the only solution. You might be able to buy some time following some of the paths suggested, like going through several discharge/charge cycles, but those typically only help when a pack is unbalanced, not when a cell is dead (though the dead cell is most often cause by an unbalanced pack, so generally you may want to adopt a discharge/charge pattern once a month for your next pack)
If it were apple that would be different, apple really has one of the best battery maintenance and charging designs in the consumer market. It's really the only reason they've been able to get away with non consumer replaceable packs for years now without a mutiny, and why other mobile devices that have gone down that path have switched back.