Using my iPhone 6 plus on iOS 9.3.1 I've just had this twice. Anyone know what it is, or had it before? I wasn't sending any iMessage or sms this came to me. I'm in UK.
I think your date and time are incorrect. Check if it's alright.
And before that, a simple restart could solve this problem. Try it first and then the time and time zone.