Search around online, and you'll find many charging problems specific to the iPhone 3GS (but not the 3G). You'll even find issues with factory car chargers that used to work with the 3G, especially with the Mini Cooper.
NOTE: This is different from iPhone 3G charging issues. That is well understood by the change from FireWire charging (using 12V, like the original iPhone) to USB charging (using 5V [plus other voltages], like the iPhone 3G).
My setup was fairly unique, as were my problems. I had a radio in my car that used a custom cable I built to attach the iPhone to the AUX-in audio for the radio. The cable also used a Griffin PowerJolt for iPod (pictured above) wired into the 12V power out from the radio to charge the iPhone. I used "switched" power from the radio, so the charger was only on when the radio was on. This worked great as a single cable charging solution for my iPhone 3G. It even solved the "not made for iPhone" message.
When I recieved my iPhone 3GS, I started having problems. The phone seemed to charge, but sometimes the phone acted like demons (not just daemons) were inside. Music playback would function, but if I received a call I couldn't pick it up. If I was able to take a call, music wouldn't play afterward. Music controls would randomly freeze so I couldn't do anything at all. Just as I was dialing a local priest for an exorcism, I had an idea...
I tried a Griffin PowerJolt for iPhone (pictured above) instead of the one designed just for iPods. Some people online said that the iPhone specific versions solved the problems they were having. It didn't.
It turns out the 3GS was starving. The problems I had only occured (or were much worse) when the battery was low. If the battery was at 90%, the problems were minimal. If the battery was at 40%, the problems were guarenteed. I took apart my solution and found the issue - the "switched" power from the radio only put out 150 milli-amps of power. Typically, USB power is around 500 milli-amps and wall chargers are known to use to 1000 milli-amps. Since the phone needed more power when the battery was low, that explained what I was seeing. It's not that Apple changed the way the 3GS charges compared to the 3G, the 3GS is just more voracious.
The solution was a little more complex though. I ended using the "unswitched" power from the radio. Using a neat thing called an automotive relay, I was able to hook both the switched power (at a max of 150ma) and the unswitched power (at a max well above 150ma). The relay acts as a switch and turns the unswitched power on and off at the same time as the switched power.
Charging problems solved!