Se estiver aberto a uma sugestão mais fácil de não utilizar a AutoKey, pode ir para Sistema - > Preferências - > Atalhos de teclado.
Apartirdaí,cliqueem"Adicionar".
Agoranomeie-ocomo"Shutdown" ou algo assim, e use "gksu shutdown -r 0" como o comando.
Agora,cliquenacélula"Atalho" para sua linha e pressione a combinação de teclas desejada.
NOTA: Estou executando o Ubuntu 11.04, mas isso deve ser aplicável.