You might be out of luck. I've got an 8700c and same thing happened. It shows up on the Nokia (like it paired) but no way will it "tether" for internet connection.
I did a lot of searching - even on blackberryforums.com - and what I found out was that there is something within the BB that prevents it from being able to actually tether with the N800 for some reason. Pair, yes; tether, no.
I've talked to others with 8700 series and they all have the same problem. I ended up getting a basic cell phone and use it to tether the N800 to the internet when I need to.
Don't know if the 8100 series is the same, but it's a definite problem on the 8700 series.