A family of Microsoft relational database management systems designed for ease of use.
I would suspect corruption, but since it works fine for you, that's less likely. However, you could compact and repair, and also try copying everything into a fresh new database - that can solve weird problems.
The most likely differences between the working and non-working scenarios are references, Access version/service packs, and permissions.
Are you logging in to the other PCs under your network user? That would help clarify any permission issues.
When you use the ACCDB, can you shift start it and see which area fails? Have you looked at the references on the failing PCs to see if they're identical?
Are the Access programs on all PCs patched to the same levels? Look in Help About.
Also, I would try deleting all linked tables from the front-end and relinking them again.