Its wild to see such different experiences. I have QC35s and they've never paired correctly with my iPhone. Part of that, I suspect, is because you have to use the stupid Bose app to pair your BT headphones. Why Bose doesn't let you pair them using the standard system is beyond me.
In the end I only use the QC35s on my laptop which is a total disappointment.