Так иногда ведет себя windows7, vindows vista.
Поскольку такое же поведение наблюдается и при установки сертификатов с другими криптографическими алгоритмами(к которым мы не имеем никакого отношения), рекомендуется задать этот вопрос компании Microsoft.

В качестве решения в большинстве случае помогает при установке сертификата выбрать хранилище вручную и указать "доверенные корневые центры сертификации".
В некоторых случаях требовалось кроме этого поставить при выборе хранилища галку "показать физические хранилища" и поставить в "доверенные корневые центры сертификации - локальный компьютер"(нужно обладать правами администратора).