Vamos por partes que fica mais fácil.
O lance é o seguinte. Você tem que colocar na linha de comando o arquivo "executável" do programa que você quer usar. No Linux não existe o arquivo ".exe" ; ele se chama ".bin" .
Então você vai até o Locais > Procurar por arquivos . Aí você coloca aMSN e selecione para ele fazer a busca no sistema de arquivos, logo abaixo, onde tem o procurar na pasta.
Bom ele vai te listar tudo o que você tiver no Sistema de arquivos com amsn. Procure pela palavra amsn na pasta /usr/bin . É esse o arquivo "executável". É ele que você tem que colocar na linha de comando. Você vai clicar no Browse do Editor de Menu e navegar até a pasta /usr/bin e seleciona este arquivo.
Pronto, acabamos a primeira etapa. Agora falta o ícone. Volte a busca que você fez, procure pelo arquivo amsn.png. note que vão existir vários arquivos, mas cada um em uma resolução diferente. Eles ficam na pasta /usr/share/amsn/icons/32x32 . Esse número no final muda conforme a resolução do ícone for maior. 48x48 ou 64x64.
Clique no botão Icon e navegue até a pasta em que fica o ícone do amsn, escolha a resolução. O 48x48 já está bom, a não ser que você goste de ícones garrafais. Pronto você acaba de colocar um ícone do amsn no Menu.
Lembre-se que a maioria dos arquivos "executáveis" do Linux ficam na pasta /usr/bin e os ícones na usr/share/nome do programa/icons . Isso pode mudar. Por isso é bom fazer a busca antes.
Espero ter ajudado. Depois me conta se deu certo.
Abraços.