MacBook shut down at 20% battery with no warning?
I had the same problem with a MacBook Pro mid-2009. Even changing the battery for a "non-official" battery did not solve the problem; I had to take it to an authorised Apple service centre; after that, no problems and still happy as the writing of this (about two years).

Any workaround that you might find online (resetting SMC and/or PRAM, recalibrating, etc) is just a temporary measure, they won't hurt at all and might give you some peace of mind.

Besides changing the battery for a new one, the Apple tech guys have special "secret" programs that can modify certain system flags and parameters.

About a year ago my MacBook Pro Retina mid-2012 (2.7 Quad i7) started with the same exact problem; the shocking news came with an estimate of $975.00 AUD to replace the battery (as it comes glued firmly to the housing you have to replace the unibody bottom including keyboard and trackpad). Still one year later the battery has not degraded at all and I still get 3-4 hours of battery life with full performance settings, but now the message has changed from "Service Battery" to "Replace soon", after this there is still a "Replace now" message.

In brief:

Service Battery means: 
There might be something wrong with your battery, or it could be nothing, but keep an eye on it.

Replace soon means:
Your battery will last less than expected, but there should be no major issues, stay alert.

Replace now means:
If you hate carrying around your charger have your battery (or the entire laptop) replaced.

Hope this helps.