I had apparently the same problem, I tryed everithigng you've suggested with no luck.
I have a bunch of users in this machine.
I've prevoiusly checked the "Available to all users" checkbox for all the wireless networks I use.
After 2 months I've got my problem solved:
All I need to do to fix the missing nm-applet was1.- Login as your first user
2.- Go to Edit Network Connections- Hope this can save you some time!
3.- Select your first network
4.- Click the Edit button
5.- Unckeck the "Available to all users"
6.- Click Apply
7.- Repeat for all connections
8.- Repeat for all users