I did some more research. The phone needed a full reset to get the functionality restored. I noticed this morning that Facetime was missing from the Settings menu also. It works fine now.
Settings -> General -> Reset -> Reset All Settings
This will reset all the settings and restart the phone. You won't lose data (music, contacts, etc.). My wallpaper was reset to the default water drops on glass like when you first activate the phone. That was easily restored though.
I recommend also disabling SMS (Settings -> General -> Messages, turn the "Send as SMS" slider to 'OFF') and then start sending some texts to people you know have iMessage working on their phone. That seems to push it through. You can always turn the SMS function back on for those people you text with who do not have iMessage if you encounter any troubles with them.