You shouldn't have to tell them to install into Trusted publishers, as the root certificate should already be there for Thawte. Try installing on a different machine and see if you get the same results.
When installing OOB with a valid cert, the install dialogs will look different than with an invalid cert. Does it look like a valid cert, or not when you install? It should of course.
Also, make sure you check the "Require elevated trust when running outside the browser" checkbox in the OOB settings.
Greg