I had the same problem two weeks ago. I contacted apple service and told me that as my battery had more than one year, they could not replace it for free, although my battery only had 208 cycles and they expect the battery to work for at least 300.
I tried all the workarounds in the forum and finally I got the problem solved.
What it worked for me was:
-Calibrate battery
-Reset PRAM
-Reset SMC
I performed the sequence two times and then, I did something slightly different.
Before the last reset of the SMC, obviously I remove the battery that was fully charged (green led). Then I pushed the power button for 5 seconds but instead replace the battery and switch the MBP on, switched it on without battery. After the system finished its start up I put the battery and the warning had disappeared. I tried this before with the battery at 99% and it didn’t work. Seemed as if it was very important that the battery is full-charged for the system to recognize it as a healthy one.
Hope it helps as your advices helped me.