New Phone Bluetooth Pairing Issues

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.