I've also had horrible data issues since "upgrading" to the iphone 4s. I would think we could at least have reliable 3g service in the middle of downtown pittsburgh!
So sorry that you’re having issue with the service! Can I have cross street info so that I can check if there is any reported outage going on at that location? I would suggest you to power cycle the device, turn of Wi-Fi and update the profile. Access data on the phone and let me know.