Did you click the 'scan' button which is located in the Bluetooth settings? Since I have Sony Headphones, I have to hold onto the power button in order for it to make the device discoverable. Perhaps such a button is located on your pair of earphone/headphones?
I used to have this problem, its because the ear buds come out of pairing mode before you can connect them, so yeah u would just try to like hold the pair button on them until you can connect but then again it depends on the brand really
I find disconnecting or coming out of pairing mode and trying again usually works. I have to do this sometimes with my Sony XM4's but it always reconnects after I do this.
