There is another scenario when this can happen:

If the assigned-macro is in a different workbook than active workbook at the time of assignment, you'll get an error.

Eg, If MyWorkbook contains the assigned macro, and if the keyboard shortcut is assigned during the MyWorkbook Deactivate event (in ThisWorkbook module), then the active workbook will NOT be MyWorkbook.

Ie, the active workbook will not be the workbook containing assigned macro.

Solution: in the assignment, qualify the macro name with the workbook name. Eg:

Code:
Application.MacroOptions Macro:="'MyWorkbook.xlsb'!SpecialMacro", Description:="", ShortcutKey:="M"


PS, minor refinement of OP:

You CAN place the assigned macro into the ThisWorkbook module (or any worksheet module). But, for it to work, you must:

-make the assigned macro public (yes, you can put Public procedures in ThisWorkbook module), and
-qualify the assignment with the module name. Eg:

Code:
Application.MacroOptions Macro:="ThisWorkbook.SpecialMacro", ShortcutKey:="M"


PPS, you might wonder, "why would someone assign a macro when the workbook is being DE-activated?"
Answer: if you're UN-assigning the macro. Eg:

Code:
Application.MacroOptions Macro:="'MyWorkbook.xlsb'!SpecialMacro", Description:="", ShortcutKey:=""