Aside from the pairing issue, are you sure that this problem wasn't caused by the fact that Sprint locked down all tethering unless you sign up for a $30/month Phone-as-Modem plan? It tends to disconnect you right away or after a minute or two.

My A900 still works great though - I just turned off Modem NAI in the debug menu and I'm back tethering. Never had a problem with disconnects, just that if I power-cycle the phone I have to re-pair it with my 770. Seems that's Samsung's issue though, not Nokia's (big surprise).