Help HTC Magic bluetooth cannot decect my headset

[Aeteus]

I just bought a bluetooth headset for my HTC Magic. The first time I turned it on my phone paired with it but would not connect. Now My phone can't even detect it when I scan for devices. It's a generic headset, does the Magic only work with certain headsets? Their website doesn't specify, it just says it works with headsets.
Thanks
The headset is made by GTMax