I am having the same Bluetooth Audio issues with a Motorola H700. As with everyone else, the device pairs correctly and shows up in all the menus. My test is to set my main sound output to go to the headset and then hit play in iTunes.
What I've noticed is that the headset will remain disconnected until something makes a sound. At that point the headset will become connected (I watch it in the bluetooth pane of System Preferences), hang for a bit (iTunes' song progress indicator does not move), and then disconnect, throwing the Bluetooth Audio Failed message. I tried the suggestion that Davey Moore posted above (on my 12'' G4 Powerbook, my G5 wont' let me turn off Bluetooth since my keyboard and mouse are both Bluetooth), but it did not work.
I watched the system log in Console.app during the whole connect/disconnect process, and the messages I get are pretty consistent every time I try this. I don't want to clog things up by pasting them all here, but here are some of the highlights....
There are a bunch of startup looking messages like performPowerStateChange and openRFCOMMChannel that all look like they are not errors. But next:
IOW late 50052784
IOBluetoothSCOAudioOutputEngine[performAudioEngineStart] 1 mBluetoothDevice->sendSCOData returns 00000000
IOBluetoothSCOAudioOutputEngine[performAudioEngineStart] 2 mBluetoothDevice->sendSCOData returns 00000000
[IOBluetoothSCOAudioDevice][incomingRFCOMMData] 9 bytes AT+VGS=7^M
This is the point when the system hangs. After a long pause...
[AppleUSBHCIController][HandleIsochData] Got error - e00002eb
[AppleUSBHCIController][HandleIsochData] Got error - e00002eb
USBF: 102379.981 IOUSBPipe[0x6436800]:ClosePipe for address 2, ep 3 had a retain count > 1. Leaking a pipe
[scoDataSendComplete] - fails new send current retainCount 15 .
[scoDataSendComplete] - fails new send current retainCount 14 .
After that it's all standard looking clean up messages. Hopefully this can be of some use to someone who knows more about what those messages might mean.
It would also be interesting to know if this problem has to do with the headset model or not. I saw above in the replies that someone is having problems with model HS810. That's the headset I used to have before it broke and I got the H700, and it always worked fine with my G5. Unfortunately I have no idea what patch that was on, but I was definitely running some version of 10.4 at the time.
Power Mac G5 Dual 2.0 GHz Mac OS X (10.4.6)