Which version of SharePoint and which version of Office? Depending on the version you may not have certain features.
Is anonymous access turned on? You may be running into an issue where the users are not actually logged in to the site. You would not be able to edit a file if you opened the file through a link and hadn't actually authenticated against the server yet.
Good luck (:
Also, there are tools you can use to snapshot a system, run the MS Office Diagnostic tool, and then snapshot the system again. "Total Uninstall" and "Advanced Uninstaller" are two that I have looked at recently. The tools compare the before and after and tell you what has changed on the file system and in the registry.