Se você usar a Autenticação no Nível de Rede em conjunto com o RDP (o que você deve porque é a opção mais segura), não será possível conectar-se se sua senha expirar. Isso significa que você não pode se conectar para alterar sua senha porque não pode se conectar a uma senha expirada. Isso é considerado por design porque não existe esse recurso no protocolo CredSSP subjacente.
Você precisará fornecer outros meios para os usuários alterarem suas senhas expiradas, como um portal de redefinição de senha de autoatendimento. (Forefront Identity Manager, por exemplo).
Como os requisitos de complexidade de senha não foram atendidos, meu palpite é que você está atingindo o outro roadblock de política de senha que raramente é mencionado - a idade mínima da senha. Se a senha foi alterada recentemente, você não poderá alterá-la novamente até que um determinado período de tempo tenha decorrido.