I'd try both.
As I said, it's odd, but it worked for me on another device.
My Zumo's connected faultlessly to my N95, Parrot SK4000, and SCALA Rider Q2. It seems to rule out the Zumo, so I'd be inclined to look thoroughly at the phone and it's settings, and maybe see if there's a firmware upgrade on the Nokia website.
Could you borrow another phone from someone to eliminate one ot the other?
If that fails, try upgrading the Zumo's firmarw (to v2.80) and see if that helps. I suspect you've already done that, though? Did I see another post about that?
Sorry this is all a bit woolly, but that's how I've always found Bluetooth!
Yoy
PS did you ever have a Kawasaki?