Arduino Nano + HC-05 AT not working

I have arduino nano + HC-05 bluetooth module.

I have used following pins D9, D10, D11 for HC-05 KEY, TX, RX and this works for data communication without any problems.

D9 pin is set to output pin HIGH (5v).

However, I want to be able to run AT commands to change default bluetooth configuration, for example to change a name.

I followed this tutorial for example just to make sure that I'm doing everything right but I wasn't able to run any of these commands.

I tried to use different speeds but without luck.

I also tried to connect KEY pin when VCC is disconnected (I read on some forum that this will change speed for programming to 38400) but same thing, nothing changed.

Any idea what else I can try?

But for some reason, this is what I'm getting as response from the code from that tutorial:

Starting config

Done!

// If you haven't configured your device before use this' '#define BLUETOOTH_SPEED 38400 //This is the default baudrate that HC-05 uses' '// If you are modifying your existing configuration, use this:' '// #define BLUETOOTH_SPEED 57600