If it doesn't work at your local Starbucks, then I'd say either you're forgetting to sign in (which sometimes brings up a signin page automatically, sometimes you have to open a browser and try to go somewhere first), or you have an issue with the Wi-Fi antennas or other Wi-Fi systems on your phone and that should be seen to by an Apple tech.
One way to double-check that its not just user error is to find or create a completely password-free open wi-fi network and try to join it.
Also, if you haven't done so in a while, I'd suggest powering down the iPhone (not just putting it to sleep, actually shutting it off) and restarting. This generally cures all ills.