Arduino Bluesmirf and Android

What I suggest is, take one set-up that you have the most information about and post that code and symptoms about that code and phone. It is good you have tried many things but at this point you need to focus on one combination only.

Then, after picking your best combination, go to programming help area, have links to your board(s), post your code, and any wiring schematics that can show your connections if you had to add wiring.