Well, it appears you have already been over the usual suspects. But it is
still possible one of them is the problem, so go back.
1) The user must have full control over the folder that contains the mdb
2) There can't be an .ldb file stuck up there from another process.
3) Another process might have a hold of the file, or failed to release its
hold on exit. It can sometimes happen that more than one connection is
opened or there has been a failed attempt.
4) Something fishy with the wire (network) - 'Shared' sometimes actually
Keep looking - one of those will be the problem 99% of the time.