Every few weeks, or after downloading and sorting a lot of books, I just back the whole contents of my Kindle up on my PC. I think the file for collections is stored in the folder ' system' . I once lost my collections and just copied the whole backup-folder 'system' to my Kindle and it worked.
Don''t know if it will work for a comple new Kindle though.
