That's right.
ALL the settings, paired phones & phonebooks, saved destinations ... are gone after the software update. I have also noticed the same bluetooth connection issue with my HTC Desire S (Android 2.3.5) phone (no problems at all before the upgrade).