Finally got this to work with AT&T myself after numerous attempts.

Upgrade the blackberry to OS 4.5.0.52 (do a google search on the web). Delete the bluetooth connection on both the N800 and the blackberry 8700. Re-pair the 2 devices and it just works. It even creates the profile for you and everything.