Buy a descent headphone :P my sennheiser MM100 does connect automatically. bluetooth has to be enabled though on the n900 before you fire up the bluetooth headset, or else the headset will go in standby mode and wont send the signal to the n900 anymore. even though when pressing the play button once on my sennheiser always connects it in 3 seconds.

Did you know that all the bluetooth devices paired and authorised are also added to a backup? few weeks ago i flashed my n900 and did a full restore of my backup. after that i didnt need to resync the headset. I really love the diversity of the backup function in the n900 its far better then every other phone out there!