I had this issue too. After enabling baseband logging (as recommended by apple engineering) and them looking at the logs, there seems to be two DNS servers 17.26.38.1 and 17.26.38.2 (For me in Houston these are the addresses). mDNSResponder tries the first server, sends two queries and switches to the second server and now the first response comes back after 13 seconds. These can be seen in packets if you filter "udp.port == 55112" in wireshark. By the time the response came back, the iphone switched to the second DNS server and doesn't accept the first response anymore.
Same behavior can be seen with (udp.port == 59101).
There are two problems here:
1) DNS servers are taking too long to respond (13 seconds!)
2) mDNSResponder not accepting responses when that happens.
For the record, this doesn't happen in beta 1 of iOS 6. It should be fixed in a future iOS 5 release. You can still take it the genius bar and see what they say. It won't hurt.