I ended up with one of these -- an iGo power extender. It's not the cheapest item that'll do the job, but it runs off AA cells ... and it has a huge range of interchangeable tips. I travel with a small pouch with the iGo and tips for: mini-USB, palm, Nokia mini, iPod, Nintendo DS, and Sony-Ericsson phone -- that's one charger, up to six different device types -- on the assumption that alkaline AA cells are ubiquitous.

(When I travel it's usually intercontinental, and it's easier to stick most of the wall warts in my hold luggage than carry all of them in my carry-on. The iGo is basically insurance against overnight delays or luggage going astray, and it works well, although I still need to keep my laptop's charger to hand.)