Put at least one book on the device, and, from the main menu, select Configuration->Maintenance->Clean_state. The database seems to go out of whack when you delete all the books behind its back.
I think it's a good idea to delete books using the Library app rather than over the USB connection, since the former keeps the database up to date with the changes (and cleans up the old book-specific data like last page read, bookmarks,...). You can delete whole folders that way, as well.