Network indicator missing but connected (16.04 LTS Unity)

1. Just for any case start with updating the package list.

   sudo apt-get update
   

   Be aware that anything further could have some minor possibility of removing an important network package, and you could got in a complicated non-network situation. So be careful and do not delete anything before you read the rest of the steps.

2. Use aptitude if possible.

   sudo aptitude
   

   (if it is installed). It is really more aggressive in resolving dependencies than apt-get or perhaps whatever GUI you're using. Have a look at the manpage, but for a quick start you can see all the broken packages by pressing "b" (which stands for broken) few times. Then just hit once "g" (which stands for go) and look at the package tree about the suggested solutions. If the solution is not deleting the whole system :) (more than a few debs) you can apply it with the second "g".

3. If you do not have aptitude or the aforementioned repair did not succeed, repair all broken packages by:

   sudo apt-get -f install
   

4. If you still had no luck, you need to fix it manually with some more time spent on solving the problem. In this case look first at the hold packages:

   apt-mark showhold 
   

   or

   dpkg --get-selections | grep hold
   

   then look at the broken packages:

   dpkg -l | grep ^..r 
   

   and then unhold the broken one that is making you mad:

   sudo apt-mark unhold package_name
   

   and try

   sudo apt-get -f install
   

   again.

Then finally you can try to install aptitude and use it for installing the package you need. If this is not successful, add to your question the list of the hold and broken packages as you may have really broken dependencies.

EDITED after extra information received from the question author

It seem that you have some PPA installed which gives higher priority to network-manager-gnome package with version 1.2.4-0ubuntu2~ubuntu16.04.1~ppa1 over the latest stable at the moment (in 16.04) 1.2.0-0ubuntu0.16.04.4. The newer package comes probably from some gnome-backport repository like gnome-backport repository like this.

Two ways to continue...

1. Revert the stable (for 16.04) version of Gnome
2. Find the missing packages from any other PPA

For scenario 1: My next suggestion is to start aptitude in interactive mode by running sudo aptitude then press slash ( "/" ) for search and write in the search field network-manager-gnome and enter. When the package is selected open it with enter and go with the arrows/pgdown to the bottom of the info page. There you can chose to install the official version "1.2.0-0ubuntu0.16.04.4" - select it and press plus (+). This will trigger the package dependency resolver of aptitude and it will try to give you a resolution. In case the hedaer goes red, this means there are some broken dependences - press several times "b" to check them...

Unfortunately the resolution most probably will be deleting all backported Gnome staff ... If you can stand it - do it. Then try to install via aptitude any further package to see in advance in what mess you can get...

For scenario 2: We need first to know the backport repository thet you're using... could be some other than this, so as suggested in the comment discussion - give the output of

egrep -v '^#|^ $' /etc/apt/sources.list /etc/apt/sources.list.d/ 

and

egrep Pin-Priority /etc/apt/preferences /etc/apt/preferences.d/*

your locate command indicates that you are missing a great deal of content from the usr/share/nm-applet/ directory. the content you are missing can be found in the network-manager-gnome_1.1.93-1ubuntu1_amd64.deb package which can be found here. If you are unable to install it by normal means dpkg has a big hammer for situations such as this and issuing the command sudo dpkg -i --force-downgrade network-manager-gnome_1.1.93-1ubuntu1_amd64.deb

If you have a current backup For an even bigger hammer you can use the --force-depends or --force-all switches

I'm not kidding about the backup. More information is available regarding dpkg force options with the command: dpkg --force-help which I have replicated below for your convenience

dpkg forcing options - control behaviour when problems found:
  warn but continue:  --force-<thing>,<thing>,...
  stop with error:    --refuse-<thing>,<thing>,... | --no-force-<thing>,...
 Forcing things:
  [!] all                Set all force options
  [*] downgrade          Replace a package with a lower version
      configure-any      Configure any package which may help this one
      hold               Process incidental packages even when on hold
      not-root           Try to (de)install things even when not root
      bad-path           PATH is missing important programs, problems likely
      bad-verify         Install a package even if it fails authenticity check
      bad-version        Process even packages with wrong versions
      overwrite          Overwrite a file from one package with another
      overwrite-diverted Overwrite a diverted file with an undiverted version
  [!] overwrite-dir      Overwrite one package's directory with another's file
  [!] unsafe-io          Do not perform safe I/O operations when unpacking
  [!] confnew            Always use the new config files, don't prompt
  [!] confold            Always use the old config files, don't prompt
  [!] confdef            Use the default option for new config files if one
                         is available, don't prompt. If no default can be found,
                         you will be prompted unless one of the confold or
                         confnew options is also given
  [!] confmiss           Always install missing config files
  [!] confask            Offer to replace config files with no new versions
  [!] architecture       Process even packages with wrong or no architecture
  [!] breaks             Install even if it would break another package
  [!] conflicts          Allow installation of conflicting packages
  [!] depends            Turn all dependency problems into warnings
  [!] depends-version    Turn dependency version problems into warnings
  [!] remove-reinstreq   Remove packages which require installation
  [!] remove-essential   Remove an essential package

WARNING - use of options marked [!] can seriously damage your installation.
Forcing options marked [*] are enabled by default.

It appears that you obtained the version you have installed from ppa:vascofalves/gnome-backports I recommend you remove this PPA from your sources.list as it's clearly stated in the description that

PPA description

Backports of GNOME packages. This is for my personal use. Don't expect anything here to work properly.

Sources:

http://packages.ubuntu.com/xenial/amd64/network-manager-gnome/download

How can PPAs be removed?

https://launchpad.net/~vascofalves/+archive/ubuntu/gnome-backports

This was a problem that was solved by using aptitude to reinstall or install network-manager-gnome, upon which I was informed that dependencies could either be resolved, or not change anything. Solving dependecies solved the problem (degraded them).