Just passing through and I saw thsi thread while I was finding out how to transfer contacts. I have a Nokia N80 (O2) and just bought a Samsung SGH-U600 (Virgin).
The way I transferred all my contacts was like this: On the N80, goto Contacts, in "Options" do "Mark All". Then in "Options" do Send (via Bluetooth when prompted). Set up Bluetooth to receive on the other phone (before you do the above) and all the contacts came over like a dream