I would say try clearing cache folders of the user who is accessing the updated assembly, (may be local file from user working directory getting opened when he tries to open assembly)
Because access rules will not work on the version basis, as you said the user is accessing same revision and same dataset.
Are they sending the structure from My Teamcenter, Structure Manager or using "File > Open" in NX?
Are they using the save Revision Rule in Teamcenter & NX? A Precise structure will load differently to a Latest Working structure. How does the structure look in Structure Manager?