I thought chas might be right, but I just disabled iMessage on my wife's iPhone and on the Mac, then disabled the option on my iPhone to send as SMS. My test message failed to deliver, but it stayed blue. I've never heard of the bubble being gray before. It's gray for incoming messages, not outgoing.
Do this... on both iPhones, open Settings, then Messages. Make sure iMessage is turned on, and optionally "Send as SMS" is on (that's for when iMessage fails). Also check the addresses in "Send & Receive" to make sure that you both don't have the same info in there for yourselves. Also make sure you have the correct contact information for each other in your own contact lists. Your own phone numbers and the email address used for iMessage should be stored.