At least for Ubuntu 12.04, the broken icon results from network-manager-gnome requesting an icon named "notification-network-disconnected" when disconnecting from a network, which is missing. In case of a wired network network-manager-gnome would prefer "notification-network-ethernet-disconnected" and in case of a wireless "notification-network-wireless-disconnected" (network-manager-applet-0.9.4.1/src/applet.c from the line 2396 on).
An easy workaround when using the GNOME icon theme would be to symlink each occurrence of "nm-no-connection.png" to "notification-network-{,ethernet-,wireless-}disconnected.png". Then rebuild the icon cache for /usr/share/icons/gnome/, e.g.:
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}
Please note that these commands fix only the GNOME icon theme, but you can easily modify them to fit your favourite theme if it provides suitable icons.