In ICS, you will should have multiple options in the drop down for network connection. Try them all. I have ATT and it lists: ICS, AT&T, Proxy.
Sometimes it will only connect using proxy, sometimes with AT&T. Don't know why. Others have also reported similarly. So far, one of them has always worked, it's just not always the same one.
I wouldn't think that you should have to uninstall PDAnet to make it work. When you enable Internet Sharing, it changes the presentation on the USB (or bluetooth) to a network connection. |