Ciao riddik86,
io non ho fin'ora avuto problemi di riconoscimento, ho provato con Nokia (vari modelli), LG GT540, HTC G1.
devo capire se è un problema software o di incompatibilità dell'hardware.
Il Bluetooth è uno standard, non penso si possa parlare di incompatibilità 
Nel senso che potrebbe non andare a buon fine il pairing, ma il modulo dovrebbe essere sempre visibile...
Forse il modulo bt era associato e connesso con altro device, quando effettuavi la ricerca con gli smartphone che hai citato?
(potrei aver detto una castronata, non ci ho provato)