Same issue, ended up manually updating the driver. Now i can connect but at speeds of less than 1 meg on a 16 meg connection. Arrg!! I have been fighting this for a week, i have called Microsoft support and been disconnected 3 times.
I checked Lenovo's site and they do not have my laptop listed as a supported Windows 8.1 device. Great, maybe that's a thought for next time, but seeing as going back to 8 is an ugly mess that may not be able to occur what do I do now? On hold with MS again, will let you know how it turns out.
When the issue first showed it was failure to connect to DNS server, and a limited connection indicator with no internet access. I could connect to other networks no problem, it was just all my existing connections that were in place before i upgraded. Also great, thanks for that. After installing the latest Broadcom Driver manually as Windows refused to use it I get connected and get through DNS, but again, what's the point at 0.3 to 1meg of speed.
And yes, all my other devices still work at full speed.
At the Intel Communities Website I posted the link to earlier the issue has been prevalent for a year. Consider yourself lucky you have only been dealing with it for a week. Like I said nothing will get done unless you post about it there and call the number I listed to get reimbursed for the Intel centrino 6235 wifi card. Be proactice people don't be lazy. It's primarily and Intel issue not Microsoft so they could care less.
Also use Wireshark and post the logs from the card.