I have had this problem for some time. It applies to both a wall charger (the one that came with iPhone and a third-party model) and a car charger (third party). Both wall and car chargers are rated at 1000 ma which should be enough power. Yet when the battery charge goes below a certain level the phone will not charge from wall or car charger, but it will charge from a computer.
I did some research on USB power. Per specification, a USB client (the iPhone) cannot draw more than 100 ma from the USB host (charger or computer or hub) unless it asks for and gets permission to draw more current. (This is so it does not interfere with other USB devices connected to the host.)
Inexpensive wall chargers do not contain any computing elements. They short the D+ and D- lines together. This makes it impossible for a client to negotiate a higher current draw, so the iPhone, working per the USB standard, limits itself to 100 ma. When connected to a computing device such as a computer or USB hub, the iPhone can negotiate a higher current, up to the 500 ma currently allowed by the USB standard.
This begs the question, why can't the iPhone charge on 100 ma when the battery is almost completely discharged? After all, when the battery has more charge, the iPhone will charge nicely from a wall charger. Perhaps someone has some insight into this aspect.
There is evidently a new USB standard for wall chargers that will fix this issue. Both the host and client must implement in order for it to work. (I haven't read the standard, but suspect it involves the client detecting that the D+ and D- lines are shorted together.) Obviously, either the charger or my iPhone 3G don't comply with this new standard. Maybe the iPhone 3GS does? Or maybe we have to wait for another iPhone model that has the hardware that complies with the new USB wall charger standard.
Meanwhile I have to be careful not to fully discharge my iPhone battery when I am away from a computer. I recently went on a 30-day trip and had no problem because I charged the phone every night. Of course, I did not use it much because it was an international trip and AT&T roaming rates are horribly expensive.