Has anyone been able to use a Bluetrek G2 Bluetooth headset with an N73?

I have tried over and over and I cannot get the N73 to see the G2.

It's not the Bluetooth set up on the phone because my old Motorola 850 works fine - if a bit crackly.

The Bluetrek headset also works perfectly with my old K750 phone.

Any ideas?