Eu resolvi esse problema removendo os aplicativos do Games for Windows Live (removi do meu computador os "Microsoft Games for Windows - LIVE" e "Microsoft Games for Windows - LIVE Redistributable") e, em seguida, baixei o programa de instalação do site e reinstalar o GFWL.
Você pode baixar o programa aqui (vá até o grande botão amarelo).