I know you said everything is up to date, but the only thing I can think of is, have you gone into the Gear app on your phone and checked to ensure your Messaging app is on the current version? I haven't had any issues with the update, especially messages. My message app didn't even need updating.