One way might be to export them from the contacts->tools-> export menu using vCard format, then copy the file over onto the new device and import them. I've transferred contacts to gmail that way and it seemed to work.