Hi Alex,
They need to import the certificate and place it in their trusted root authority box first and then try to open it. The 2nd time, they should see the checkbox. Let us know if you need more information.
Patrick Halstead [InfoPath MVP]
InfoPath Dev Seattle
Patrick Halstead
Project Manager at Qdabra