AT-09 (HM-10 clone) BLE Bluetooth module does not show up with new name

Hey,

I've just replaced my older HM-05 bluetooth module with a new HM-10 clone (identified as an AT-09) which I connected to my Arduino ATMega according to this tutorial (with the addition of a voltage divider between the Arduino TX and the AT-09 RX to adjust to 3.3V). And the problem is, that when I give it a new name, it does not show when pairing from other devices. There it still has its factory default name.

I'm using the below code to interface the AT-09 through my ATMega which is connected to my Windows computer. Set up like this, I can connect to the module (found as device "MLT-BT05") from my iPhone with the "BLE Terminal" App and from a Samsung Tablet with the "Serial Bluetooth Terminal" App without any problems (one at a time, of course), receiving sent messages on the respective other side.

When not paired with any other device, I can enter AT mode and adjust the settings, f.e. the name (see dialog below). As shown, it saves the new name but this new name is not displayed on the iPhone or Samsung Tablet when searching for devices, there it still shows the factory default "MLT-BT05".

Is there an explanation for this or did I miss something important while adjusting the settings? Any help would be appreciated! (I've reset all settings to factory default, set a new name again and it still does not work)

AT+NAME
+NAME=MLT-BT05
AT+NAMEDevice1
+NAME=Device1
OK
AT+NAME
+NAME=Device1

char c = ' ';
boolean NL = true;

void setup()
{
  Serial.begin(9600);
  Serial.print("Sketch:   ");   Serial.println(__FILE__);
  Serial.print("Uploaded: ");   Serial.println(__DATE__);
  Serial.println(" ");

  Serial3.begin(9600);
  Serial.println("Serial3 started at 9600");

  Serial.println("");
}

void loop()
{

  // Read from the Bluetooth module and send to the Arduino Serial Monitor
  if (Serial3.available())
  {
    c = Serial3.read();
    Serial.write(c);
  }


  // Read from the Serial Monitor and send to the Bluetooth module
  if (Serial.available())
  {
    c = Serial.read();
    Serial3.write(c);

    // Echo the user input to the main window. The ">" character indicates the user entered text.
    if (NL) {
      Serial.print(">");
      NL = false;
    }
    Serial.write(c);
    if (c == 10) {
      NL = true;
    }
  }
}