I am almost embarrassed how long this took me to figure out. FaceTime was missing on my iPhone 4. Apparently, if you upgrade from 3 to 4 it doesn’t automatically show up. Instead you need to go to Settings and then tap on the Phone settings. Right there, staring back at you is a screen that says FaceTime and it gives you the ability to turn it ON or OFF.
Tap ON and it should reappear in your apps (required me to reboot to show up).