So decided to call applecare. They were able to rectify the situation on both phones.
1. Go to Facetime and Messages. Make sure ONLY your apple id email address and cell phone number show up as ways you can be reached.
2. Toggle Messages off, then back on.
This resolved the issue on both of our 6S's.
I just tried this. Hoping it works. My girlfriend and I have been getting the verification message off and on over the past couple weeks on her 6 and my 6s.