Al FireFox y al aMSN no le salen sus iconos por una sencilla razón, no son binarios como tal, el archivo firefox es un lanzador para el binario real (un script) y el amsn es un script escrito en tcl/tk. Para que te hagas una idea, un script vienen a ser como los .BAT de DOS.
Pero siempre puedes ponerle tú uno, haciendo un enlace al escritorio (por ejemplo), y haciendo click en las propiedades en el icono (hablo de KDE).