Eh dipende dove l'avevi.
Se erano su un telefono nokia o windows mobile basta fare l'export in file csv (o separato da virgola) dall'ovi suite o da outlook, poi li importi su gmail, nel tab contatti, e da questo momento in poi li gestisci da li, ogni volta che ti connetti ad internet anche tramite wifi lui li aggiorna tra telefono e gmail.
Se invece erano sulla sim fai l'import secco dalla rubrica nell'account gmail dall'applicazione base di android, poi fa tutto lui e li sincronizza su internet.