Congratulations PhiI! I can feel your relief
I'm stuck in a similar situation. Band 2sees 950XL,phone doesn't see Band.
I've tried everything suggested in this forum and yours looks like it should work (albeit substituting an iPhone 5 for the Android phone - which, of course works perfectly with my Band 2).
I'm wondering whether you can just add a few more (*****'s Guide) steps to your process as to when and when Bluetooth was turned on and off and when you reset your device and/or reinstall the App. I figure I'm getting something wrong as the fix isn't working for me and I just can't crack it.
I realise you posted a while ago and maybe you've forgotten those details and moved on...if so, I don't blame you, it's so frustrating!
Mine was working fine until I had to soft reset my 950XL and now all this trouble!
Here are the steps I followed to get mine to finally work:
Just got it to work.
In my situation where I could always pair my Band 2 to my Nexus 6 without fail I followed these steps to get my Band 2 to finally work with my Lumia 950XL.
1) Start Add Band process on my Nexus 6. On my Band 2 I selected Windows Phone instead of Android (Not sure this is needed but it seemed logical to me).
2) Finish successfully adding the Band to my Nexus 6 and turned off Bluetooth on my Nexus 6.
3) On my Lumia 950XL I uninstalled and reinstalled MS Health App and I had the My Microsoft Band option but when hitting it you can't actually see the Band 2 information.
4) On my Band 2 I went to settings and Bluetooth and turned it off, turned it to 'pairing' and it asks if I'm pairing to iPhone and I said no. Waited for pair between 950XL and Band 2. After successful pairing I went into MS Health App and I am able to use everything just like on my Android but now with the added ability to use Cortana.
I'm thrilled, and hope this works/helps for anyone else in the same situation.
-Phil