When it happened to me, it was an issue in the books.db file on the storage card. (I don't store books on the internal memory.)
There's a table in the database called collections which stores the list of books in each collection. It turned out that for each book that was meant to be in the collection, there were two entries -- one had the correct ID for the book on the storage card (e.g. 4294967364), and the other was 2^32 less (e.g. 68). Deleting those incorrect entries (using SQLiteSpy or sqlite3 or similar) cleared up the collections.
I *think* the query I used to clean it up was:
DELETE FROM collections WHERE content_id NOT IN (select _id FROM books);
But it's not happening at the moment so I can't test. Next time I trip over it I'll take better notes.
The idea is there though -- if a book doesn't exist, it shouldn't be in any collections.
I'm not sure whether the source of the problem is a Calibre bug or just Calibre tickling a bug in the T1; it hasn't bothered me enough to investigate more.