In the Enterprise PDM Administration Tool, you may want to check the user settings under 'Reference Dialog' and be sure that 'Always work with the latest version of files.' is checked.
Depending on the refresh settings you have set for client, database, archive updates it can take up to (i think) a minute on default settings before clients become aware that there is a new version.
When you say they are experiencing problems, what exactly is it? are they receiving errors (through the ui or in client logs) is it slower than they expect? Does it simply not respond?
The issue has been that they had been logging in and working on the wrong drawings. But since we got our message notification system up and running it hasn't been as big of an issue.