Wurden die Bluetooth Geräte schon einmal aus der Liste gelöscht und noch einmal mit dem iPhone verbunden?
Wenn das letzte iOS Update über Wlan gemacht wurde, dann könnte es auch helfen, das iPhone auf die Werkseinstellungen zurückzusetzen. Damit könnte man ein Softwareproblem ausschließen, speziell wenn man erst einmal ohne ein Backup die Bluetooth Verbindung testet.
iPhone, iPad oder iPod touch auf die Werkseinstellungen zurücksetzen - Apple Support