Решение:

Для проверки подписи штампа времени нужен сертификат службы штампов времени, которым этот штамп подписан.
Этот сертификат может находиться:
1.В штампе (для этого нужно настроить службу или добавлять --cert-req при использовании tsputil).
2.В хранилище «Другие пользователи»