It's intentional. If you're logged into and using another iOS device, the watch will not provide the notification. This is a feature to preserve battery life, and a good one. Why notify you via the watch if you already using your iPhone?
Try repairing. That's what I have to do with my Pebble every so often.
What's that?
Sorry, forgot the hyphen. Re-Pairing. Disconnect the Apple Watch from the phone then re-connect it.
Have you tried opening the watch app on your phone and looking at the notification settings for messages?