What model watch do you have and/or what version of Tizen is it on. On the GW3 with latest software, there is an option on the watch to connect to a new phone. Settings-Connect to New Phone (last option under settings). Is this how you attempted to connect to your new phone?