I've got a car charger that worked great with my 3G. Then the "gravity fairy" visited and I wound up with a 4GS. Well, I'd get that complaint whenever I started the car with the phone plugged in. But if I pull the cord on the iPhone end and plug it back in, everyone is happy, the phone charges with no nasty gram. I have one of those clock radios with the iPhone adapter. The phone charges nicely while the unit is plugged in, but if I turn it on I get the same message. I pull the phone and stick it back in and it works.
Interestingly, I also get this message if I use my Apple charging block and cable, both of which came with the 3G (the ones supplied with the 4GS work fine). If I plug the block in after the phone, I get the error. Plug the cable into the phone last and it works great.
WTF? I don't know and don't care. I know how to make it work so I'm happy.