What Saltin says, is only half-right.
In a domain structure, assuming that no specific EFS recovery agent has been specified (so the Default Domain policy has set it to Domain\Administrator):
When a user is logged in, and attempts to encrypt a file, EFS will query the users certificate store for an EFS enabled key. If it doesn't find one, it will automatically generate a 101 year local certificate for the user, and use that key to encrypt the data. So, removing the key will only be a problem for the user when they try to get back to their OLD data. They will still have the ability to create NEW files.
To disable EFS in the domain, you have to set a GPO with an EMPTY EFS Recovery Policy, and make sure that it over-writes the default policy. (See the MS TechNet and White Papers on how to do this.)
Your issue is likely to be EFS, as that is the (misleading) error message that comes back when you try to access an encrypted file. If you look at the properties (attributes) of the files, look for the letter E--which means the file is encrypted. Alternatively, you can run efsinfo against the file or directory, and it will tell you if the file is encrypted, and if so, which user encrypted it.