I bought a ridiculously cheap (£3.13 inc p&p) bluetooth mouse from a no-name in China (from an almost empty Pay-Pal account, I'm not that gullible) fully expecting it not to work but nothing ventured, nothing gained.
And sure enough the Gemini didn't see it, but after refreshing the bluetooth several times and randomly (and dementedly) pressing buttons on the mouse the Gemini eventually saw it, and still sees it after powering down.
So moral of the story is; don't give up after one or two goes, keep resetting and make sure the device you want to pair is active.