I just read a recommendation for a battery replacement site in the Amazon website's Kindle forum, and it looks like it sells replacement batteries for a variety of e-readers, tablets, GPS, smart phones and other hand-held devices. WOT rates their website as okay. I've never used them but it looks like they also include video instructions with the batteries, which is a nice touch.
I figured it might be worth a try for those of you whose e-reader's batteries have died or are on their way to doing so.
http://www.newpower99.com/default.asp