If this still keeps happening with the cryptographic service running, it is probably because your catalog database is corrupted. This is a fairly common problem and Microsoft has published a
knowledge base article on how to fix it.
The problem can appear with various error messages, in many different situations, so don't be discouraged by the length of the KB article and just skip to the "Resolution" part.
