Maybe stupid-answer.Did you turn off BT on your iPhone before pairing with the Android.Leo..
IOS is picky inasmuch that it only talks BT4. You don't say what bluetooth you are using, but the fact that you have used it with IOS at least confirms that it is BT4. Years ago I had a tablet that would not talk to my HC-06 but it turned out to be fine with a bluietooth keyboard. I never found out what that was about. I have an HM-10 that my neither my tablet nor my phone will connect with. I have not yet pursued this problem as the HC-06 is fine with both. I guess these things can happen. If it is a chronic problem, I guess we would all know. Plenty of people on this forum use BT-4 these days.
For the most part, Android has always lagged well behind iOS when it comes to the Bluetooth implementation. Ian.
I know my previous was not too helpful but I was only saying Android<>Bluetooth does see the odd bug. - however rare. Bluetooth with Android is common reliable and popular. I guess it depends on what you want, but I don't think Arduino<>Bluetooth<>IOS merits one second's consideration. At first I would suggest you try the new phone on other bluetooth devices. I say this because you are familiar with Bluetooth operations, and the problem is not likely to rest there. You should not have to buy another Bluetooth but, for less than $4, I would chance an HC-06 or HC-05, which are known fine performers with Android. The HC-05 is more versatile than an HC-06 but costs about the same. Both are BT-2 devices. I think an HC-08 is more likely to be just moving the problem rather than solving it. I have just realised that this might be a protocol problem, and you don't say what you want to do - or used to do.
What I want to do: send characters/data between the Android and the Arduino