Hi
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. (Some permissions will not be accessed but it will fix the issue)
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.
A reboot was required to fix the tray.