I believe it may have something to do with your carrier. The reports I've read about Sprint CDMA phones had to do with a hack found on a Sprint users forum that allowed the phone "tethered" access. Although BT is not tethered, the same hack applies to the phone and it allows access to the DATA network from the phone side.

It sounds like the N800 is seeing and sending OK and the phone is doing what it's supposed to for a BT connection. They phone may not know where to go for DATA and so it says C'ya to the attempt.