Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.
Here's what worked for me. YMMV.

• Deleted 9.1 beta profiles on both watch and phone.
• Powered Off both devices.
• Powered On both devices.
• iOS 2 showed up as available in my Watch app on iPhone. The rest was pretty textbook.

I did not have to reset network or any of the other work arounds mentioned here and elsewhere.

Going luck!
 
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.