We have given all users full access to the folders, following a bit of playing around with the office partner source code it turns out that the error is produced by a call to CoCreateInstance, this is returning the result Interface Not Supported. As far as I can tell all of the registry entries for calls to setvalue have full access to all users, logically as there are around 4000 registry commands from this one api call I have not been able to check for sure that the users have read access to all the rest of the registry values, but think they do.