Comment 20 for bug 70718

You have to switch to the old inquiry mode with "sudo hciconfig hci0 inqmode 0". Starting with bluez-utils-3.x the best available inquiry mode will be selected by default and this is not gonna change. You have to fix gnome-bluetooth.