As the developer of Phone Amego, I see many customer reports including some like this:

"I am trying to use an iPhone and my MacBookAir - Lion 10.7.2 - which seems to work more or less (Phone Amgeo 1.3.3). However, on my Mac Mini, same configuration it doesn't. I can call, and monitored calls show up etc, but when I try to connect the speakerphone (i.e. computer), the console spits out an error, see below."

22/11/2011 09:53:38.000 kernel: [SendHCIRequestFormatted] ### ERROR: [0x0407] (Add SCO Connection) -- Send request failed (err = 0x0010 (kBluetoothHCIErrorHostTimeout))
22/11/2011 09:53:38.000 kernel: REQUIRE_NO_ERR failure: 0x10 - file: /SourceCache/IOBluetoothFamily/IOBluetoothFamily-4010.4.4/Core/Family/Drivers/IOBluetoothSCOAudioDriver/IOBluetoothSCOAudioDevice.cpp:882

Here's another case where it works fine on the customers MacBook Pro, but fails on a 2009 Mac Pro with an identical configuration.

Jan 19 10:21:46 kernel[0]: [SendHCIRequestFormatted] ### ERROR: [0x0407] (Add SCO Connection) -- Send request failed (err = 0x0010 (kBluetoothHCIErrorHostTimeout))
Jan 19 10:21:46 kernel[0]: REQUIRE_NO_ERR failure: 0x10 - file: /SourceCache/IOBluetoothFamily/IOBluetoothFamily-4010.4.4/Core/Family/Drivers/IOBluetoothSCOAudioDriver/IOBluetoothSCOAudioDevice.cpp:882

The customer's theory was that something about the Broadcom chipset used for Bluetooth on this system is different causing it to fail. To test his theory, he ordered a 3rd party Bluetooth USB dongle to try and surprisingly it worked. Details follow.

[---Email from Simon--->
I have some good news. I overnighted the BT dongle I told you about and sure as you know what it works like a charm. Downside of using this over built in BT stack is it cannot wake the Mac but apart from that works beautifully. This is a broad com chipset as well but later model and supports BT class 3.0. There is an IOGear unit support class 4.0 (iPhone 4S uses 4.0) which I would love to try as well when it comes out in March but in the meantime this does it.

So for any other users of yours with a 2009 Mac Pro or that are experiencing issues like I did I would highly suggest that they take a look at this $24 investment. I have included the link below:

Make sure you go into Bluetooth Explorer (part of the dev pack with Xcode) and reset the BT stack in there including the following:

Full Factory Reset
Recant Connect Apple Devices
Delete Link Keys From BT Module
Delete Global Bluetooth Preference File
Delete All Link Keys From Software
Restart BT Daemon
Remove All Configured Devices

{For what its worth I did the above on the internal stack before gaining the new dongle and it didn't work however I would highly recommend the steps above be performed before plugging in the new dongle to clean the standard stack out}

Then when that is done, turn off the BT (Built In BT Stack) from the menu and shut down the Mac. After this plug in the Medialink dongle and turn the Mac back on. You will then notice BT becomes active again but just for this dongle therefore bypassing and turning off the built in stack.

Then go and setup your devices as you would normally.
<---Email from Simon---]

As much as I would like Bluetooth audio to be simple and transparent, some Bluetooth issues are beyond the scope of Phone Amego to solve. See Understanding the Relationship between Phone Amego and Bluetooth. If you do encounter a problem, I welcome the opportunity to share information that may be helpful to others.