I had this same problem.
I restored from backup from my old 3G running 4.0 and face-time didn't exist on my phone.
I went back and reset to factory settings and "set up as new iPhone" and everything works fine. This was easy for me as I use google sync.
I went back to restoring from my 3G and face-time again was gone.
Repeat.
I did that on my most recent restore. Still nada. I guess I'll try it again. I used Mac Address Book to sync my contacts and left everything fresh otherwise. Still got nothing.