I played a lot with HC-05 and HC-06 until I understand the way they work. Now i've big Android App communicating with HC at 115200 bauds and sending and receving heavy data.
I hope these tips will help you and other guys and save you time:
1) the way the HC-05 and HC-06 detect end of AT command is different:
HC-05 (can be slave and master): each AT command must end by CRLF. So or you add CRLF in your Android code or you select the option "CRLF line ending" in your console.
HC-06 (only slave): need a "time" between AT Command. According to the data sheet if there is more than 1 sec, the HC consider this is the end. Even if your question is about the HC-05 I think it can be VERY interesting to understand the big problem which can happened with the "delay" between AT.
If you use a communication at 9600 bauds and type AT commands on serial monitor and echo both what HC reply and what you send, you will have such things: type AT+VERSION and see on serial monitor AT+OVKERSION Why ? Because as the delay between each char is long, as soon as the HC had receive "AT" he thinks that's the command and start to reply "OK".
So with a HC-06 you must send the AT command in one "shoot" and then add a delay of 2 sec to be sure.
2) Problem of settings.
The HC save the speed you set as the name and the pin code. So trying to set the pin, name and speed in the setup funcion is not usefull as at each time the Arduino will reset, each time you'll try to set the data.
Also, factory setting of HC seems to be 9600 bauds.
So you have to create a small sketch, which you'll use only ONE time to set the HC. Like this:
Serial.begin(9600);
delay(2000);
// AT+NAMEXXX where XXX is the new name
Serial.print("AT+NAMEJOHNDOO");
delay(2000);
// AT+PINXXXX where XXXX new code (4 number)
Serial.print("AT+PIN1999");
delay(2000);
// AT+BAUDX where X from 1 to 8
// 1 -> 1200 Bauds
// 2 -> 2400 Bauds
// 3 -> 4800 Bauds
// 4 -> 9600 Bauds
// 5 -> 19200 Bauds
// 6 -> 38400 Bauds
// 7 -> 57600 Bauds
// 8 -> 115200 Bauds
Serial.print("AT+BAUD8");
This for HC-06. For HC-05 you must add CRLF and you don't need the delay.
Important: as, at the end of this sketch, the HC is now at 115200 bauds, you must havea serial.begin(115200) for comunicating with it. If you run this sketch two time, the second run will do nothing as the Arduino will try to comunicate at 9600 bauds with a HC listening at 115200.
3) Problem of speed.
On the Arduino, you can use the software serial lib only if you plan to send and receive at up to 19200 bauds. Some say it work at 38400 but I've had problems at this speed.
The best way it to avoid Software serial and use directly the basic RX and TX of the Arduino. Using that you can run at 115200 without any problem.
Even if this answer is a bit "outside the question" I hope this will help you working with the HC.