I have similar problem using the bluetooth shield, some phone are not able to see the Arduino while other can...
The code to initialize the BT connection it's just the same as you are using and I keep the baud rate to 38400...
This is an example with video that explain how it works using a Samsung 9003, while if I try to search Arduino and the related BT shiel using a Samsung Next I cannot find the device:-(
This is the link showing how it works on Samsung 9003, what is wrong? Any suggestion?
This is the BT setup source I use
blueToothSerial.begin(38400); //Set BluetoothBee BaudRate to default baud rate 38400
blueToothSerial.print("\r\n+STWMOD=0\r\n"); //set the bluetooth work in slave mode
blueToothSerial.print("\r\n+STNA=E-Scooter\r\n"); //set the bluetooth name as "SeeedBTSlave"
blueToothSerial.print("\r\n+STOAUT=1\r\n"); // Permit Paired device to connect me
blueToothSerial.print("\r\n+STAUTO=0\r\n"); // Auto-connection should be forbidden here
delay(2000); // This delay is required.
blueToothSerial.print("\r\n+INQ=1\r\n"); //make the slave bluetooth inquirable
Serial.println("The slave bluetooth is inquirable!");
delay(2000); // This delay is required.
blueToothSerial.flush();