Hi Michael,
Your BT Module is better than mine 
Specifically because you can change its mode between Master and Slave. I may have to get me one of those
The module must be set to Slave mode, I suspect that your other phones can't see it either but otherwise when it is set correctly it should display a fairly rapidly blinking LED (which is blinking evenly) and then it is 'discoverable' so you can go into bluetooth settings and 'scan for devices' to find it.
Firstly congratulations on purchasing both bits! You purchased the bluetooth module plus the backplane where it is really easy to accidentally purchase just the bluetooth module without the backplane or just the backplane without the bluetooth module everyone should read the posts on my forum at BTInterface.com before purchasing one!
By default when its found your module should show up as 'HC-05' (mine is 'Linvor').
Otherwise its the same as mine, you don't need to connect those extra two pins up, Key or State, you just need the power pins and the TX/RX.
Note that even without the TX & RX pins connected to anything and only with the power pins connected if the module is in the correct mode (Slave mode) then the LED will flash and you can scan for it and find it and pair with it from any bluetooth phone (mine flashes at a constant 4 hertz (ish)).
So I suspect that your only problem is that it is in Master mode and as such IT is the one who would do the discovering and not the other phones.
You can change its mode by issuing AT commands to it (modems anyone )
You can issue AT commands only while it is not paired and connected.
Use your terminal app to just send the two letters AT ... try with lower case, then upper case, when it is working sending the command AT will get it to send back 'Ok'
You may have to try different settings in your terminal app. For the Arduino its called the 'Serial Monitor' and it may or may not require a 'line ending', I leave mine set to 9600 baud which is the default that the Bluetooth module comes set at and the default that BTinterface works at.
In mine it must be an uppercase AT to get it to return OK
Then you can issue AT commands to it, and one of the commands that you need to issue to yours is the one to put it into Slave mode.
By the way you can also do other cool things with AT commands such as:
AT+VERSION returns the software version' This is a harmless command to send, use this to make sure you are sending AT commands correctly.
Note it must be exactly as above, AT in uppercase then the plus sign and then the word VERSION also in uppercase, then mine returns: OKlinvorV1.5
AT + NAMEname Returns OKname max 20 chars so for example issuing the command AT+NAMEBTInterface.com changes the module's name to BTInterface.com so when it is in Slave/Discover mode that's what you'll see when you scan for devices Remember that when you make your cool doohickeys.
AT+PINxxxx Returns OK setpin You can change the password!!! usually set at 1234 you can use this to change it to something else... be careful!!!
AT+BAUD1 Returns OK1200 'now set to 1200 baud
AT+BAUD2 Returns OK2400 'now set to 2400 baud
table: (you want number 4)
AT+BAUD4 to set it to 9600 baud which is the rate that BTInterface is designed for.
1 1200
2 2400
3 4800
4 9600
5 19200
6 38400
7 57600
8 115200
9 230400
A 460800
B 921600
C 1382400
I would leave it set to the default 9600 baud, note that if you change the baud all of a sudden you may start receiving rubbish characters in your serial monitor, that's cause you have to now change the serial monitor's baud rate to match
And now.... tadaaaaa...... you will need to issue the command:
AT+ROLE=0
To set it to slave mode.
Lastly, I lied about those AT commands above, it would seem that they are different for the HC-05 as attested to in this really REALLY horrible manual that I found...
I saved it on my website here:
http://www.btinterface.com/btinterface/HC-Serial-Bluetooth-Products-201104.pdf
Note that when they write 'salve' they mean 'slave' ...
Even more lastly I didn't lie about the AT+ROLE=0 command, that one is from this HC manual so try this first.
The correct AT commands for the HC-05 are in the horrid manual.
Hey everyone please join my forum on BTInterface.com and I'll be glad to help with all aspects of Bluetooth doohickeying
ian