O ícone do menu principal no Ubuntu usa o nome "distributor-logo.png". Se o pacote que vc. instalar tiver um ícone com esse nome, ele será alterado. Se não tiver, não haverá alteração.
Experimente criar um ícone com esse nome (obviamente, usando sua imagem preferida e o tamanho correto) e colocá-lo na pasta "apps" do tema que vc. está usando (temas locais, instalados por vc., estão em "~/.icons" e gerais, instalados pelo root via APT, em "usr/share/icons"). Ele não só será o ícone utilizado no menu principal mas também o do "sobre o Ubuntu" (veja vc. mesmo).
Finalmente, a solução do link que vc. citou funciona para qualquer tema de ícones, já que se trata de uma alteração de configuração do Gnome via "gconf-editor". Procure aqui no Fórum que vc. acha explicações mais detalhadas de como fazer o que foi proposto no link, ou seja, alterar o ícone do menu via "gconf-editor".