Primeiro, se você configurar a implantação no modo Por usuário, não verá falhas de conexão devido à falta de licenças.
Do que você disse, 2 de 10 CALs foram emitidas para dois usuários que se conectaram com sucesso, o que significa que o servidor de licenciamento e a configuração de licenciamento do RDSH estão funcionando bem.
O problema parece estar no RDSH, você pode tentar remover as políticas locais apenas para ter certeza de que não é o problema.
Se isso não funcionar, eu começaria de construir meu RDSH.