I just bought my watch, and I'm having the same problem sending a message to an android phone. Did you find a solution yet? It doesn't make sense that I can send, or reply to, with my phone but not with my watch. I already have an appointment to bring it in since it couldn't be solved over the phone, but I'd love to be able to find a fix and cancel the appointment.
Edited to add that mine will only work if iMessage is switched off.