The half-amp of +5 on the USB should be plenty to charge the Kindle, and even charge and power it while web surfing at the same time I would think.
One thing to look at (if you have thte radio on) is the little wireless indicator. If the antenna icon has a "1x" at the top instead of the ((.)) thing, then it's in 1xRTT fallback mode which supposedly uses more juice. Also if you're only getting a bar or so of signal then the device could be spending time hunting for signal and/or operating at higher transmitter power, both of which will suck the juice out faster than an EV-DO link with 4-5 bars of signal.