Form templates and documents are linked.
A document retains a link to the location the template was published and expects it to be there.
Are you publishing to a network file share or web server?
The security is all handled by IE. You would want to make sure the server hosting the template is in the intranet or trusted security zone.
Obviously check the permissions on the template, everyone who uses documents would need read permissions on the form, and in a file share scenario, I believe need write permissions in the folder that is is located in. I think I remember something about that at some point, so maybe worth a try.
Lastly, make sure they are accessing it the way it was published. Make sure you are using the publishing wizard to deploy the form, not just copying the xsn out there. Have a local copy and publish the form to its network or web location.
During the publishing process you will specifyy how the users will access the template. htttp://... or at \\server\share etc. I have seen where people have various mapped drives or access ti different ways and this will not work either. It will only work the way it was published.
You can cleanup the XML files manually and with notepad either change the link or look at how the old forms were accessing the form. It is in the header of the XML.
Good Luck