Stupid question, but I'm only asking since you didn't directly state it, are you running iOS 9 on your phone? watchOS 2 requires iOS 9, if you're still on 8, it won't show up.
Yep, I'm on iOS 9. I guess I could restore the iPhone just to see if that triggers it. Otherwise I'll probably wait until an app I use on the AW updates to give me some incentive.