Are you running the queries through VBA or through the GUI by simply double-clicking on them?
Is the database split? Each user has their own copy of the front-end locate locally on their PC? Linked tables are married using UNC or IP and not mapped drive? When was the last time the databases (back-end and front-end) were compacted? What is your current build number, bitness and update channel? Have you tried updating our reverting your Office installation?