I've used my 6800 with both a traditional hands-free headset (some entry level Plantronics model) and a pair of decent athletic bluetooth headphones (Motorola S9). The Motorola sounds phenomenal, and the Plantronics sounds...well, just like a crappy bluetooth headset should. :-p
Does your headset support the high end protocols? Also, make sure that you have a ROM with the proper bluetooth protocol enabled. I think it's called A2DP, and (please forgive me if I am mistaken) some of the early stock and custom ROMs didn't support it. I currently use the Windows Mobile 6.5 ver 21202 beta 1.0 by TPlane37 available here and it works:
http://forum.xda-developers.com/showthread.php?t=497303
I'd try attaching the phone to a different headset, and the headset to a different phone. Trying a different ROM may help, too. I'd do all this to isolate whether the problem is the phone hardware, ROM or the earpeice.
Good luck!
Ivan