What do you mean with "Released the screw"?!
In which state is the screw then?! Does the user have read permissions for that state?!
The screw is in "Released" state, like after you would Peer Review, or Data Load Bypass. We all have permissions to use it in this state, even the admin with all permissions was having the problem. If it is "In Work" state, the assembly finds it fine. Once we change it to "Released" it can't find it even though the reference path is pointing right to it.
After some exploring, I found a sub-assembly further up the tree that used the same screw. The reference link for that had been broken so I guess trying to find the same screw in two different places was confusing solidworks. I checked out said sub-assembly, replaced the screw up there, and now it opens without problems.
Thanks for your response though Carsten!