I just activated a new iphone 4s and restored from a backup of my former iphone 3gs - had the same problem - Waiting for Activation on both facetime and imessage. I tried all the usual fixes, reset all, hard reset, turn facetime/imessage on and off, and on and on. 2 hours on phone with tech support to no avail.
I just found the fix on my own - no clue if it will work for everyone. But it's ridiculously easy and worth a shot so you don't waste hours and hours resetting/synching as I did.
All I did was go into settings>phone>my number - erase it by touching the ">". Then re-enter it making sure to input with the "+" and country code. For example in the US: +1(508) 569-9901
No hard reset necessary. I went into settings>facetime and imessage, immediately after inputting my phone number again and the dreaded "waiting for activation" message was gone. I tested sending a message - came thru to the other party fine and facetiming another device (my mom's ipad some distance away) and it rang thru with everything working properly i.e., video/audio.