I am also seeing this problem. The connection appears to drop even if I don't attempt the 'hcitool auth' command. Below is the output from 'hcidump -X -V'. I am using Ubuntu Hardy, all up to date and current with standard repositories. My headset is Nokia BH-501.

john@roadwork:~$ dpkg -l bluez*
Desired=Unknown/Install/Remove/Purge/Hold
| Status=Not/Installed/Config-f/Unpacked/Failed-cfg/Half-inst/t-aWait/T-pend
|/ Err?=(none)/Hold/Reinst-required/X=both-problems (Status,Err: uppercase=bad)
||/ Name                      Version                   Description
+++-=========================-=========================-==================================================================
ii  bluez-audio               3.26-0ubuntu6             Bluetooth audio support
ii  bluez-btsco               1:0.50-0ubuntu2           Bluez Bluetooth SCO tool
ii  bluez-cups                3.26-0ubuntu6             Bluetooth printer driver for CUPS
un  bluez-firmware            <none>                    (no description available)
ii  bluez-gnome               0.25-0ubuntu1             Bluetooth utilities for GNOME
ii  bluez-hcidump             1.40-0ubuntu1             Analyses Bluetooth HCI packets
un  bluez-pan                 <none>                    (no description available)
un  bluez-passkey-gnome       <none>                    (no description available)
un  bluez-sdp                 <none>                    (no description available)
ii  bluez-utils               3.26-0ubuntu6             Bluetooth tools and daemons


HCI sniffer - Bluetooth packet analyzer ver 1.40
device: hci0 snap_len: 1028 filter: 0xffffffff

< HCI Command: Create Connection (0x01|0x0005) plen 13
    bdaddr 00:0D:3C:A6:E8:1C ptype 0xcc18 rswitch 0x01 clkoffset 0x0000
    Packet type: DM1 DM3 DM5 DH1 DH3 DH5 
> HCI Event: Command Status (0x0f) plen 4
    Create Connection (0x01|0x0005) status 0x00 ncmd 1
> HCI Event: Connect Complete (0x03) plen 11
    status 0x00 handle 11 bdaddr 00:0D:3C:A6:E8:1C type ACL encrypt 0x00
< ACL data: handle 11 flags 0x02 dlen 10
    L2CAP(s): Info req: type 2
< HCI Command: Read Remote Supported Features (0x01|0x001b) plen 2
    handle 11
> HCI Event: Read Remote Supported Features (0x0b) plen 11
    status 0x00 handle 11
    Features: 0xff 0xff 0x8f 0x78 0x18 0x18 0x00 0x80
> HCI Event: Command Status (0x0f) plen 4
    Read Remote Supported Features (0x01|0x001b) status 0x00 ncmd 1
< HCI Command: Write Link Policy Settings (0x02|0x000d) plen 4
    handle 11 policy 0x0f
    Link policy: RSWITCH HOLD SNIFF PARK 
> HCI Event: Command Complete (0x0e) plen 6
    Write Link Policy Settings (0x02|0x000d) ncmd 1
    status 0x00 handle 11
< HCI Command: Remote Name Request (0x01|0x0019) plen 10
    bdaddr 00:0D:3C:A6:E8:1C mode 2 clkoffset 0x0000
> HCI Event: Command Status (0x0f) plen 4
    Remote Name Request (0x01|0x0019) status 0x00 ncmd 1
> HCI Event: Page Scan Repetition Mode Change (0x20) plen 7
    bdaddr 00:0D:3C:A6:E8:1C mode 1
> HCI Event: Max Slots Change (0x1b) plen 3
    handle 11 slots 5
> ACL data: handle 11 flags 0x02 dlen 16
    L2CAP(s): Info rsp: type 2 result 0
      Extended feature mask 0x0000
> HCI Event: Remote Name Req Complete (0x07) plen 255
    status 0x00 bdaddr 00:0D:3C:A6:E8:1C name 'Nokia BH-501'
> HCI Event: Number of Completed Packets (0x13) plen 5
    handle 11 packets 1
< HCI Command: Disconnect (0x01|0x0006) plen 3
    handle 11 reason 0x13
    Reason: Remote User Terminated Connection
> HCI Event: Command Status (0x0f) plen 4
    Disconnect (0x01|0x0006) status 0x00 ncmd 1
> HCI Event: Disconn Complete (0x05) plen 4
    status 0x00 handle 11 reason 0x16
    Reason: Connection Terminated by Local Host