EFS Remote Encryption

We have been trying to setup EFS across our domain.
Unfortunately Reading/Writing file over network share does not work, we get an "Access Denied" error.

Another worrying fact is that I managed to get it working for 1 machine but no other would work.

The machines are all Windows 2008R2, running as VM under ESXi host.

According to: http://technet.microsoft.com/en-us/library/bb457116.aspx#EHAA

• We setup the involved machine to be trusted for delegation
• The user are not restricted and can be trusted for delegation.
• The users have logged-in on both side and can read/write
  encrypted files without issues locally.

I enabled Kerberos logging in the registry and this is the relevant logs that I get on the machine that has the encrypted files.
In order for all certificate that the user possess (Only Key Name changes):

Event ID 5058: Audit Success, "Other System Events"

Key file operation.
Subject:
    Security ID:        {MyDOMAIN}\{MyID}
    Account Name:       {MyID}
    Account Domain:     {MyDOMAIN}
    Logon ID:       0xbXXXXXXX

Cryptographic Parameters:
    Provider Name:  Microsoft Software Key Storage Provider
    Algorithm Name: Not Available.
    Key Name:   {CE885431-9B4F-47C2-8415-2D766B999999}
    Key Type:   User key.

Key File Operation Information:
    File Path:  C:\Users\{MyID}\AppData\Roaming\Microsoft\Crypto\RSA\S-1-5-21-4585646465656-260371901-2912106767-1207\66099999999991e891f187e791277da03d_dfe9ecd8-31c4-4b0f-9b57-6fd3cab90760

        Operation:  Read persisted key from file.
    Return Code:    0x0[/code]

Event ID 5061: Audit Faillure, "System Intergrity"

[code]Cryptographic operation.
Subject:
Security ID:        {MyDOMAIN}\{MyID}
    Account Name:       {MyID}
    Account Domain:     {MyDOMAIN}
    Logon ID:       0xbXXXXXXX

Cryptographic Parameters:
    Provider Name:  Microsoft Software Key Storage Provider
    Algorithm Name: RSA
    Key Name:   {CE885431-9B4F-47C2-8415-2D766B999999}
    Key Type:   User key.

Cryptographic Operation:
    Operation:  Open Key.
    Return Code:    0x8009000b

Could this be related to this error from the
CryptAcquireContext function

NTE_BAD_KEY_STATE 0x8009000BL 
The user password has changed since the private keys were encrypted.

The problem is that the users I using at the moment can not change their password.