Sorry for reviving an old thread. But I have this same issue with my N810 and my E71. It is driving me nuts. I had a SE W910i I used for dialup, and it would work about 6/10 times. Got annoying, but it did work eventually.

I upgraded to a E71 and I have never got it to dial up ever.

My suspicion is that the E series wont do BT DUN without the Nokia PC Suit. If this proves to be true I will be mighty pissed.