Like most people I've been looking for an N800 case too (I searched and searched for the official product, but with zero joy), so here are the results of my searching for your benefit.

These guys do a decent-looking leather case:
http://www.proporta.com/F02/PPF02P05...260&t_mode=des (UK)
http://www.proporta.com/F02/PPF02P05...260&t_mode=des (US)
(I love the way us Brits get stitched on pricing, £26.95 vs $34.95!)

These US-based guys do a good range of accessories for the N800:
http://www.boxwave.com/products/easy...ories_2569.htm
And here's their equivalent leather case, which also looks reasonable:
http://www.boxwave.com/products/dlsl...leeve_2569.htm
And a 'FlexiSkin' rubbery number, if you're into that:
http://www.boxwave.com/products/flex...-n800_2569.htm

I checked Amazon but couldn't find much through a direct search.

Shopping.com had the leather and rubbery cases:
http://www.shopping.com/xFS?KW=Nokia...T=SCH&x=23&y=6

And so did eBay:
http://preview.tinyurl.com/28k9kh (the eBay URL was ridiculous!)

May you all have beautifully protected N800's!

PS I love Nokia (never had anything other than Nokia), but WHY do they have to make it such a pain to get certain things from them?!