Network shows NOT CONNECTED when it really is

I found a solution for (my version of) this problem.  My tray icon never showed the red X, but if I clicked on the icon, the popup showed a bigger icon with a red X, and said "Not connected".  As in your case, Internet worked, but I'm unable to setup a VPN connection because it insists on using a non-existent modem, obviously because I'm "not connected" (which I am). 

I monitored the processes running the NlaSvc and Netprofm services (using ProcMon), and noticed that both were denied read/write access to subkeys within the HKLM\SOFTWARE\Microsoft\Windows NT\CurrentVersion\NetworkList hierarchy.  

The processes were running as NetworkService and LocalService, respectively, so I tried adding full access for these service accounts to the entire subkey mentioned above.  Notice that permissions are not automatically inherited in the registry, so you may need to explicitly "replace all child object permissions with inheritable permissions from this object".

Within seconds, Network and Sharing Center tells me I'm connected to my domain.  Yay!

A reboot was required to fix the tray icon and its popup.