I have this resolved.
The scenerio above occurs when System ODBC connections are created via control panel on the machine.
The DB works perfectly when I created a DSN file and placed it in the same folder as the DB on a mapped network drive available to all clients. I then re-linked the tables one last time via the file, and the DB can now be opened on any machine and connect to the DB without error.
I think this is due to the "Workstation ID" stored with the login information in the Access DB for the ODBC connections created through control panel. This information isn't present in the DSN file.