I second tubemonkey's suggestion, and actually go case crazy with my gadgets: they all have a sleeve around their cases, because I also carry a glass bottle with me, so I need the extra protection. You could even up the degree of protection by chosing a padded zippered sleeve instead of a neoprene sleeve, which, of course, should fit the kindle AND its case.
This is the type of sleeve I mean, or a timbuk2 like
this one.