Did the charger include the "made for iPhone" certification when purchased including for the 3GS?
Your iPod Classic can be charged via USB or Firewire. The original iPhone can be charged via USB or Firewire, but the FireWire pins were removed from the iPhone's dock connector after the original iPhone which is also the same with all iPod models now. If your car charger charges via FireWire, this wouldn't work with the 3GS regardless. If a 3rd party device does not include the "made for iPhone" certification, this doesn't mean it won't work with the iPhone but having the certification ensures it - unless the device has failed.
If there were something wrong with your iPhone, it wouldn't be charging when connected to your computer or to the wall charger either.
If the charger includes the "made for iPhone" certification, contact the manufacturer. If not, purchase one that does.