Is everyone shared drive name the same?
Does everyone have the shared drive named drive X:(any letter will do, but it has to be the same)
If not, Infopath can't find the template when your users are opening locally saved forms.
Why?
InfoPath stores the File path to the template in the saved form inside the headers, and since your forms are stored on a shared drive, if your shared drive is drive M: and one user is drive O: and another is drive X:, but the path to the template is M:\path to template, only users who have that particular shared drive named M: will be able to use it. It will always work the first time though, since there is no save file yet.
The only way I can think of to fix it would be to choose shared drive letter Z: and have everyone use it for that shared drive, I don't know if that is possible for you, but that would prevent this from happening form today forward. This will not fix from today backwards, you would have ot manually edit those saved files to point to the new location of the template.
Does all that makes sense?