Foi um problema de driver e foi isso que eu fiz. Eu escrevo tudo o que fiz, mesmo que não fizesse parte da solução.
Primeiro, atualizei o BIOS e habilitei o Power on by PME novamente. Ainda não funciona. Então eu instalei um pacote chamado firmware-realtek mas ainda não está funcionando. Se eu adicionei a letra b como eu transmiti em "Wake-on: bg", de repente, funciona porque permite ativar para todas as transmissões na rede. Os pacotes mágicos ainda não funcionavam, então provavelmente era algo com o dispositivo de rede, afinal. Então eu instalei outro driver do site realteks e agora está funcionando como um encanto. Está até funcionando quando o computador está completamente desligado.
Depois eu desinstalei o pacote firmware-realtek e ele ainda funciona, mas não sei se a atualização do BIOS tinha que fazer alguma coisa com o sucesso. Após a segunda instalação do driver, o Wake-on: g não era mais padrão, então eu tive que fazer essas mudanças como o wiki debian descrito.
Os drivers da Realtek podem ser encontrados aqui www.realtek.com.tw/downloads/downloadsView.aspx?Langid=1&PNid=13&PFid=5&Level=5&Conn=4&DownTypeID=3&GetDown=false