You tried running it directly from C:\Program Files\Microsoft Dynamics CRM\tools\Microsoft.Crm.DeploymentManager.exe
And you get a message that the file cannot be found...? In that case maybe you have a permission problem on that file or it's corrupted..