gen23:
I tried getting my module in AT mode but it didn't change anything.
Does that mean that you had success with AT+NAME? and it bounced back HC-05 or something?
That you have two not working out is odd.
I have a Samsung and, a few weeks ago, I got names on the list and could pair OK, but never an opportunity to connect. I gave up on the first app and found a winner in the second (Bluetooth Terminal). Not your situation, but I'm not just jousting at this as a theoretical exercise.
Have you paired your Android with any other devices?