Could the two problems be related: missing XREFs also means AutoCAD deos not know where to go to find and open your files?

Yes, you do need to relink all references if you did not make the effort to maintain all full address paths when changing files locations as seen from each user's computer.