Patience apparently worked for me, because I don't know exactly what I did to fix it. Skip to last paragraph for what I did do.
First of all, I've had the same issues noted above, after updating iOS7 on my AT&T iPhone 4. On several apps (facebook, Yahoo Fantasy, Weather, Google, etc), I'd get the "connect to itunes to use push notification". It was especially bad on Yahoo Fantasy Football since it would pop up immediately after clicking OK. Additionally, iMessage, Facetime, and Find My iPhone would not work. It kept telling me "waiting for activation" on iMessage and Facetime or would tell me to check my network connection and not sign me in. Texting without iMessage was costly for me.
Happy to say that all is well now, but it got worse before it got better. I looked through all of the suggestions I could find on this forum short of doing the "restore to backup" option. I've done that once before and refuse to go through that process again and lose purchased app data. I also can't believe that an iOS7 improvement/update should cause people to have to reset/restore their iPhone. Incredible.
Anyway, the last thing I did before everything started working was to try again to turn off iMessage and Facetime in "Settings", logout of iTunes/Appstore, turn off Location Services for FindMyPhone (Settings/Privacy/Locations Services/very bottom), and delete FindMyPhone. I rebooted the phone and then did a hard reboot twice (or whatever you call the Home+Power 10sec restart). After a long long wait for loading, I went to Settings. When I tried to click on "Messages", it just highlighted the word and froze. Closed "Settings" and tried clicking "Facetime" and got the same frozen highlighted reaction. Ugh!! Even worse than previous attempts. I think I tried reloading FindMyPhone and location setting. Then went back to try Messages and Facetime and maybe did another reboot. Just when I was ready to toss my phone and go droid shopping, the Apple angels paid me a visit around midnight and without any other explanation allowed me to turn on iMessages and Facetime without saying "waiting for activation" and likewise I didn't get a "connect to itunes" pop-up when I checked to see my Yahoo fantasy team still had a fighting chance even after the Dallas debacle on SNF. I will not be the first to update to next iOS.