Well being a fellow modem guy you obviously know about AT commands, I built a 300baud modem for my commodore 64 once 
If the device is set to slave mode then the only thing I can think of why it might not work with BTInterface is the baudrate.
Should be 9600 for BTInterface which is usually the default for these modules.
I suspect that the hardware of these modules is the same and this guy called Byron made a reflasher:
To flash the software where I believe I could flash the HC-05 software on to my module which I think is the HC-06 (slave only).
If it is the same hardware then I can assure you that it works fine on the 5v Arduino, should work between 3.3 and 6v.
All BTInterface does is start the Android pairing process which you can do manually if you prefer.
Once the device is paired it should be just a normal serial bluetooth device although I have noticed that it always says 'paired but not connected' even while it is sending and receiving to it
You say
the problem is your app doesn't connect when other devices can.
Do you mean 'where other software can' ? Can you connect other apps but not mine?
There's another app called ArduinoCommander, can you get that one to work with your module? on the same Android device?
Its just that I'm not sure if its something to do with the Android device or if its specific to BTInterface?
In any case I thank you for trying BTInterface
ian