iOS - Bluetooth not auto connecting to previously paired device
Apparently a lot of headset devices can maintain a list of several devices. So did my Skull Candy Ink'd Wireless.

The trick to reset this list, was to power up the device and hold - and + for a few (5?) seconds till you hear a strange beep. Then I paired again and the auto-connect worked again. 

My guess is that it didn't like to be connected to multiple iPhones and got confused somehow.