I have the same problem with Mobile Internet Sharing (tethering) and have posted a query here and on the Vodafone eforum.
I had it working on 2 PCs (my destop to test it out, then onto wife's laptop for use while away from home). All working OK then................it stopped.
First thing I asked myself (IT background) was 'what has changed?' Well, I reckon it's the Android system upgrade as you also found trouble after it. The solution being offered (after a lot of head scratching) is a factory reset as you have done but will i lose my data (pics not a problem), phone directory and apps?
Thanks, Chris.