I know there was no real response to this thread, but just in case anyone looked this up and is interested:
My problem solved itself. I tried for 24 hours to get both devices to work simultaneously, and having given up, I got into the car the next day, and Bluetooth was good as gold, connecting flawlessly! And it's worked ever since. I have no idea why, it's absolutely nothing that I did, it just decided to work! Bluetooth is weird!