interesting...
i've had THE EXACT SAME problem about a month ago, also we were talking about it here:
bottom line there was about this:
As said before is probably due to some android's bt broadcomm module bug that does not allow to find Class of device code 0x00
and some semi working workarrounds.
as a result, i bought a new bluetooth module LM-400 and got it up and running in no time (after i figured out that the AT commands from the manual are outdated -> new firmware was on it).
did anyone else have any luck with the method sam_92 suggested a few posts up, so i know if i should take the shield i was already upset about for not working from the box again and give it another try?