RemoteApp Credentials incorrect

We run access to a specific place through Remote App Services, before now the client machine just clicks on the .rdp and presses enter at the credentials screen and they are in.

Recently we imposed new passwords on the client machines and since then the credentials for the client on the remote app (should be taking credentials from server) is initially coming up as incorrect, we are able to click on ok and then select user and press enter again and they are in, but this should be ok on initial run.

Any ideas on the possible cause?