Can't discover HC-05 Bluetooth ONLY on Android

Hi there, here goes my first post.

I have a HC-05 device that I have connected to my Arduino Pro Mini at 5V. I was able to sniff the HC-05 on an iphone while it was connected to a motor controller. I just paired it with my windows PC while its hooked up on the Arduino as well (even though the LED starts blinking again after a minute or so.).

On the Android side on the other hand, I can not even discover the HC-05 on Bluetooth settings. How come I can pair with an iPhone but not an Android device? what could be the issue? The LED is blinking normally.

Many thanks in advance
-Orkun

Possibly inadequate power.