Iphone 3GS not charging
that's a tough one and could be an issue with a bad battery or something wrong with the "charging circuitry" in the phone itself which would require a visit to the Genius Bar or a 3rd party phone repair shop.

One thing you might want to try before going that route is to plug it into the Mac or PC that you normally sync with. Does it give you that same error? If so it may be that there is an issue with the connector. Either in the phone itself or the dock connector. You can try blowing in there to dislodge any lint/dust/dirt but a quick spurt of canned air would be my recommended method. Do both the connection port on the phone and the dock end of the connector and try again.

It is possible that the connector is worn and jiggling the connector in various ways might point to that.