I had major issues trying to discover Bluetooth devices through HCI; same results as you - friendly name resolution and discovery couldn't be performed (though I could connect if I knew the address...) Sifting through the BlueZ documentation and many forum posts - the general consensus was that HCI had been deprecated in favour of DBUS methods.

Use D-BUS to communicate with BlueZ. It works!