Te cuento como lo hice yo cuando pasé de un Nokia 5800 a un Motorola Defy:
Pasé mis contactos al outlook (eso ya lo has hecho tu), despues exporté los contactos en un formato (que ahora no recuerdo) y despues ese archivo lo importé con gmail.
Por lo que veo ahora, gmail tiene muchas mas opciones de esas. Ve a tu cuenta de gmail en un ordenador, ve a preferencias, y ahí tienes 2 opciones:
Puedes añadir la cuenta de correo que contiene esos contactos, o puedes darle a importar y meter los datos ahi. Ve mirando.
ACTUALIZO: Así lo hice yo:
http://office.microsoft.com/es-es/ou...001148902.aspx
En gmail, ve a contactos, despues a importar, y sigue esas instrucciones. Ya me contarás.