Well, I'm using Finnish as the system language, so "Shut Down..." is not what reads in my Apple Menu for shutdown. Once I realised that the menu title has to match that of the shutdown menu, in my case "Sammuta...", I tried that. Surprisingly, it did work when I defined "Option+O" for the shortcut, but didn't work with "F12" (Fn+F12). Eventually, I defined it as "Option+Command+S", which seems a convenient combination for me.
So, if your Mac uses a language other than English, go check the Apple Menu for the name of the shutdown menu title. Now use that exact title for creating a shutdown shortcut (you don't need to include the three dots "...").
Hope this solves the problem :)