My 4S won't see my wife's new 5S as iMessage-capable -- how to fix?
I'd try to Reset Network Settings, as detailed here: Not receiving Text Messages after upgrade to iOS 7 -- this seems to cure a wide range of ills for Messages.