Pretty much any Bluetooth phone will work, even the cheaper ones, as long as it supports the DUN profile. I've used a Nokia 3110 Classic and 5300 without any problems. It doesn't have to be Nokia though.

However, if you want the fastest connections, you ought to get a 3G or 3.5G phone which is slightly pricier, though even in this area the prices are coming down (and prices of smartphones are coming down too BTW).