You may see this message when using the latest version of the iOS app.

This is an issue with the software installed on the micro:bit. 

1: Program ("Flash") this hex file (attached) onto your micro:bit via USB (instructions here) to get the latest version of the micro:bit pairing software.

2: Before any kind of Bluetooth communication with the phone or tablet (pairing or flashing), enter pairing mode

3: Pair your micro:bit with the app using 'Choose micro:bit'