Comment 38 for bug 284994

For known device problems:

If you delete the device from the list, it should ask for a pin the next time, but you might need to exit the wizard and/or preferences and restart the process. This has worked for me.

Also some devices don't require passcodes so will pair without them, or worse, the bluetooth subsystem "remembers" the WRONG details (I had a similar problem on my Nokia tablet - a headset wouldn't connect though was paired and deleted and re-paired several times)

You would need to find and manually delete any entries from /var/lib/bluetooth/(adapteraddress)/* referring to the device, or stop bluetooth, wipe all the entries in the directory and re-pair (pun intended) everything, and restart the bluetooth system.

I can't easily duplicate the problem but if it happens, I'll try to find the entry that needs to be deleted. Somewhere in the bluez stack, if a device is deleted, it needs to be purged (all references removed) or at least a purge option should be given. Or perhaps purge all unpaired devices or something similar, but there may be a simpler fix.