Had exactly the same issue running Windows 7 (win7). Connected to the Internet but status showing no connections and a red cross on the network icon. Problem also caused problems connecting to Lync and Office365 as well as VPN, which apparently uses the status to check if connectivity is available.
Found the solution here: http://social.technet.microsoft.com/Forums/en/w7itpronetworking/thread/df17c593-e78f-4878-97b0-7569307934c5
Apparently some permissions gets wrong in the Registration Database and needs to be fixed using RegEdit. The solution is a step by step and might be solved just by deleting a cache folder using RegEdit and potentially setting some permissions.
Hope it helps.