Fixo !!!
Para qualquer pessoa com o mesmo problema no futuro:
Eu fui para o link e baixei o RegDACL.
Eu então executei o seguinte comando:
regdacl HKLM\SOFTWARE\Classes\.map\OpenWithProgids /gga:F /ggu:R
Isso deu permissões completas aos administradores e usuários. Eu não precisava ter me incomodado com os usuários, mas hey ho.