Pelo menos para o Ubuntu 12.04, o ícone quebrado é o resultado do network-manager-gnome solicitando um ícone chamado notification-network-disconnected ao se desconectar de uma rede, que está faltando. No caso de uma rede cabeada, o network-manager-gnome preferiria notification-network-ethernet-disconnected e, no caso de um sem fio notification-network-wireless-disconnected ( network-manager-applet-0.9.4.1/src/applet.c da linha 2396 em diante).
Uma solução simples ao usar o tema de ícone do GNOME seria vincular cada ocorrência de nm-no-connection.png a notification-network-{,ethernet-,wireless-}disconnected.png . Em seguida, recrie o cache de ícones para /usr/share/icons/gnome/ , por exemplo:
export iconTheme=/usr/share/icons/gnome
for px in 16 22 24 32 48 256 ; do sudo ln -s ${iconTheme}/${px}x${px}/status/nm-no-connection.png ${iconTheme}/${px}x${px}/status/notification-network-disconnected.png ; done
for px in 16 22 24 32 48 256 ; do sudo ln -s ${iconTheme}/${px}x${px}/status/nm-no-connection.png ${iconTheme}/${px}x${px}/status/notification-network-ethernet-disconnected.png ; done
for px in 16 22 24 32 48 256 ; do sudo ln -s ${iconTheme}/${px}x${px}/status/nm-no-connection.png ${iconTheme}/${px}x${px}/status/notification-network-wireless-disconnected.png ; done
sudo update-icon-caches ${iconTheme}
Por favor, note que estes comandos consertam apenas o tema de ícones do GNOME, mas você pode facilmente modificá-los para se adequar ao seu tema favorito se ele fornecer ícones adequados.