On investigation of the issue in the Windows Logs\Application there is a Warning related to Exchange "An exception occurred and was handled by Exchange ActiveSync. This may have been caused by an outdated or corrupted Exchange ActiveSync device partnership." This did not reference the problematic user.
The first stage was to view the ActiveSync DeviceID Associations with the users, this can be done by using the following PowerShell command;
|
Get-ActiveSyncDevice | ft
UserDisplayName, DeviceID
|
This will display all of the users that have an associated ActiveSync device to their Exchange account. The user that was having problems had two entries.
I then logged into the Exchange ECP from a web browser, if it's enabled in your environment you can normally connect up to it using your namespace followed by /ECP. Then click on the Manage My Organization button and choose Another User....
Try the username of the problematic user, and click OK.
You then click on Phone and Mobile Phones from the left hand side menu. As you can see there is two entries for the iPhone. I selected them both and used the X button to delete the entries.
It will ask you to confirm if you would like to remove the device, click Yes. Please note this will not Wipe the device.
On the problematic iPhone I then tried to re-add the Exchange account and it worked correctly.