I too have a new Lenovo (G505s) and have been messing with this problem for hours. This is the only fix that has worked, but thought I would share my other findings.
I couldn't connect to my wireless network, which I have had no problems with on my other Windows 7 PCs. Apple devices such as phones and tablets have reported slower broadband speeds in the last couple of months but Windows based tests show the full speed
I should be receiving. My broadband is Virgin Cable delivered through a Superhub set to modem only mode, passed to a Netgear router acting as a DHCP server with wireless turned off. This is hard wired to another Netgear router downstairs acting as a Wireless
Access Point and is set to AP mode.
This setup has worked fine until recently when I thought the Access Point router was failing on the wireless side as everything connected to this router via cable was fine, including this new Lenovo G505s running Windows 8.1. My Lenovo T410i connects to
the wireless on both 2.4 and 5GHz bands, with the latter showing 450Mbps.
I thought the new Windows 8.1 G505s must have a faulty Wireless card but yesterday I took it round to a friend's house and it connected to their BT hub with no problems with the Driver set to the stock Broadcom 802.11n. Reassured that the wireless card
was not at fault, I researched the 'Default gateway is not available' problem and found this fix. Reset the driver to the Broadcom 802.11a device and suddenly I am connected to the internet, and the dreaded 'Limited' banner does not appear by my home wireless
network any more. I am typing this on the G505s over wireless now.
I have written all of this to highlight the fact that there may be a compatibility issue with Windows 8.1, some network devices and certain ISPs. As I mentioned, I couldn't get the hardware to work with Virgin and Netgear but COULD with BTs wireless Hub.
Applying the Broadcom 802.11a fix as a device driver fixed the Lenovo G505s to work with Virgin and Netgear with Windows 8.1, but I think my wireless a connection speed will now be limited to a lower speed for all wireless network connections than the wireless
n speed I may be able to achieve on some other wireless networks under the 802.11n driver. Still, working is better than not.
I hope this reassures others struggling with the same problem. Try other people's wireless networks to see if you can connect there before you give up!
Thanks for the fix. Sanity preserved.