As others have previously mentioned, I too upgraded my launch (July 2010) iPhone 4 32 GB AT&T (GSM) to iOS 7 and FaceTime still does not work. Just to be certain I erased my phone and restored from my iCloud backup (while in iOS 7) and FaceTime still wouldn't work.
I was thinking of testing a bit further, but I don't have high hopes. I was thinking of going into 'Settings > iCloud > Storage & Backup > Manage Storage > Selecting 'This iPhone' backup > Delete Backup' to remove all backups. Then going back in and re-enabling iCloud Backup so it will take a fresh new backup of my data (now that iOS 7 is installed), then trying to restore from this new backup.
Alternatively, I was thinking of going into 'Settings > iCloud > Storage & Backup > Manage Storage > Selecting 'This iPhone' backup > Delete Backup' to remove all backups. Then going back in and re-enabling iCloud Backup so it will take a fresh new backup of my data. After this I was considering going into Manage Storage and de-selecting (turning off) everything under the backup options. This way my camera roll and app data would not be backed up when it takes a fresh backup. After the new fresh backup is created with all backup options de-selected, I was thinking of restoring from this backup again and testing FaceTime. I was going to make sure I backed up my photos and videos to my computer first though.
From everything I've read on all of the posts though, I doubt either option I mentioned above will cause FaceTime to work.
This does make me wonder though on people who have erased all of their phones content and started from a "clean slate" if FaceTime is still working after some time or if the issue has arisen again. I also wonder if the ones who got FaceTime working by starting fresh, have a recent backup, and, if by chance they restore from that backup, if FaceTime would stop working again?