Hey,

There is a rather extensive list over at maemo.org with lots of phones tested.
http://maemo.org/maemowiki/BluetoothDUN

Personally, I use a Nokia 6280 with my N800, and it works like a charm - took 10 seconds setting it up (pairing) and then it just works straight out of the box. Also it's not the most expensive phone even though it is one of the better ones.

Good luck with your connection :-)

// Kny