Eu fiz as alterações, mas segui assim.
Fui em usr/share/icons/boulevard, onde boulevard é o tema atual que uso, dentro dele fui na pasta scalable/apps.
Ali está os icones do menu, no caso usei imagens de 128x128, copiando o nome da original e trocando pela a que eu queria, nem precisei entrar como root.
As vezes só substituir funcionava, mas teve dois que tive que excluir primeiro, e depois colar o que eu queria devidamente renomeado.
Troquei o do menu aplicações e do menu de logon/logoff
No caso do pezinho que tirei fora, troquei tanto o distributor-logo.png quanto o start-here.png.
Caso queira trocar outros é só olhar pela figura e o nome deles originais, copiar o nome, renomear o icone desejado e substituir.
Abraço.