Finally resolved the issue by doing the following
1) Removed user from being a deployment administrator by removing it from the Deployment Manager console (Please note that trying to remove the user using PowerShell commandlet Remove-CrmDeploymentManager resulted in the error "System User xxx is not a deployment manager".
2) Removed the user from the table [SystemUser] and [SystemUserAuthentication].
3) Adding the user again as deployment administrator by running the PowerShell commandlet "New -CrmDeploymentAdministrator.
It's a bit strange the Microsoft Dynamics Crm errors when deleting users using powershell and allows it to be deleted from Deployment Manager console.