Copiei os arquivos .remmina de volta ao atualizar de 11.10 para 12.04
Descobri que isso está acontecendo somente no Windows 2008. Possivelmente um problema no RDP6.
Isso foi resolvido porque a segurança de alguma forma foi redefinida para 'Negociar'. Alterei Advanced / Security para 'RDP' e tudo está funcionando novamente.