My scenario and fix:
Ipod Nano 7th gen paired previously with Jaybird X3 bluetooth headphones.
At some point the X3s stopped connecting with the Ipod (connection failed message from Ipod Nano)
I chose to "Forget this device" in Nano interface in the hopes that would reset the connection after X3s were discovered again. No luck. In fact the X3s were not discoverable at all! Other devices were appearing in the Ipod Nanos BT discover screen..and X3s worked with another device via bluetooth.
I reset the Ipod using menu select button and sleep/wake button for 6 secs.
No luck.
Restored Ipod using the iTunes software from Apple. No change, X3s not found.
And erased all data..
Watched this YouTube on how to enter diagnostic mode on Ipod:
Followed the instructions. Narrator said to press all buttons simultaneously for 3 iterations...I think this is wrong and diagnostic mode will engage after apple logo appears on first try..
Once the Ipod was in Diagnostic mode I went through all menu items. I am not 100% sure how the system was repaired but I would definitely navigate to the BT test (bluetooth self-test) and run that.. there was also a DRAm self test but I doubt that test would result in any connectivity change.
After rebooting the Ipod the X3 headphones immediately responded to pairing..
I hope this helps :)