michaelreyes is correct, I've been pairing with the 1.1 phone OS, and just today paired with the 1.5 phone OS for everything that doesn't require data.
The data connection issue is multipart. Firstly, T-Mobile doesn't allow Bluetooth tethering, as such there are no applications available from the Market. There are some 3rd party markets that will sell Bluetooth tethering software if you have root access to your phone. Unfortunately, the 3rd obstacle is that the only available tethering solutions (even home spun) create PAN connections whereas the TT devices only support DUN. If either you can create a DUN connection on the phone, or TT adds PAN support, I believe it will be possible for rooted phones to support data, but that currently isn't the case.