I've had this problem for 3 months thru various iterations of both iOS and watchOS. My 4 trips to the store haven't done a thing. They don't know anything, they only offer the most basic, rudimentary GUESSES about how to fix the issue. Thus far, they've had me unpair/repair the watch, restore the watch from a backup, set the watch up as new. Most recent unfruitful "solutions" they've offered are erasing/restoring the iPhone, which I've done, and setting the phone up as new, which they can go play in traffic about.
How I have $1500 in Apple's latest tech on my person and not have one of the most basic, most FUNDAMENTAL features not work thru multiple updates not only breaks my heart, it chaps my aß.
One of the most frustrating things about this is that when it does happen, I don't get a haptic notification on my phone, either. So, no notification AT ALL other the visual screen. Effing pathetic.