I went to the Apple store today to get a car charger. The third party one my wife has for her original iPhone triggers the "not supported" message, but it still charges her phone. I was too chicken to leave it plugged into the 3G so I don't know if it would have worked.
I was surprised that there are only third party car chargers (no Apple). The salesguy told me that people were having problems and that I should wait. I did see a charger that was simply a USB socket. It would allow you to use the cable that comes with the 3G. Next trip to the store I'll buy one and see how it works.