I just wanted to update this for others searching with the same problem.
This problem only affected some of my security usergroups, and actual table and query permissions seemed to have no bearing on this error happening (my Read Only usergroup worked fine, but some groups with all but admin privileges were affected). Since this temporary table is not accessible from the security/permissions GUI, I was unable to fix the problem there.
I did list all tabledefs and querydefs; the table was not shown.
In the end I had to create a new blank .mdb file, import all objects, and re-do security permissions. Now all usergroups are able to refresh table links with no problem.
Hope this helps someone in the future.