I have the code at the beginning which changes the baud rate, changing it in command mode didn't help either.
I included the following in setup according to the hookup guide.
bluetooth.begin(115200); // The Bluetooth Mate defaults to 115200bps
bluetooth.print("$"); // Print three times individually
bluetooth.print("$");
bluetooth.print("$"); // Enter command mode
delay(1000); // Short delay, wait for the Mate to send back CMD
bluetooth.println("U,9600,N"); // Temporarily Change the baudrate to 9600, no parity
// 115200 can be too fast at times for NewSoftSerial to relay the data reliably
bluetooth.begin(9600); // Start bluetooth serial at 9600
[/code]