I have a Griffin car charger that I bought when I got my 3G and found that my old charger for my iPod/original iPhone wouldn't work. It comes in two parts, the car plug has a USB socket on it and there's a usb to dock connector lead.
I plugged my new 3GS in, and it gives the charging not supported message. I plug the 3G back in, it charges. I made sure the connectors were clean etc., no joy. There's no problem with the 3GS, and when I bought a new, different make of charger from an O2 shop, that worked fine.
It would see that there is *something* different between the 3g and 3GS, even if Apple haven't announced it.