Eu encontrei uma solução. Como dito anteriormente, minhas macros foram definidas em Normal.dotm. Eles estavam em um módulo de código chamado Module1.
Eu criei um novo módulo chamado Module2 e depois cortei & colou todas as macros neste novo módulo. Depois disso, as teclas de atalho estão funcionando perfeitamente para as macros. Eu também deletei o Module1.
Este é claramente um bug raro e estranho no Word 2007. Provavelmente foi causado (de alguma forma) por tomar meu Normal.dotm da minha antiga instalação do Windows XP e copiá-lo para o novo Windows 7 e Word 2007.