I don't know if this will help anyone, but I upgraded my iPhone from IOS 5.1 to 6.1 today and saw similar wifi issues. I have an iPhone 4 and an Airport Extreme basestation. My phone never had any problems when running IOS 5.1 but once it was upgraded to IOS 6.1 I had similar issues everyone is complaining about.
What I saw was my phone would sometimes get an IP address and other times would self assign an address. When it did get a valid IP address, webpages still would not load or sometimes would start loading and eventually fail.
I tried everything people were talking about, restarting the phone, the router, resetting network settings, etc. I even tried restoring the phone again and not applying my backup so the phone was "clean". Same problem.
Then I looked at my Airport Extreme wireless settings. I had my 2.4GHz network set on a specific channel. When I changed it to automatic the phone finally started working. When I changed back to a fixed channel the phone stopped working. Back to automatic, the phone works. For me at least, it seams like setting the airport channel manually is causing my problems. I even tried setting it to automatic, testing the phone works, finding the channel being used, setting that working channel manually and the phone does not work. It makes no sense to me but setting the channel to automatic is working for now......
If this is the problem then I can only assume I will have huge problems using public wifi and hotspots since I am sure they set channels manually. I'll have to spend a little time seeing how well it works in the wild.