Yo si voy a la seccion de contactos y sin entrar en ninguno le doy al botón de opciones, ya me pone "Eliminar contacto" y desde ahí me deja seleccionar varios para eliminar los que quiero.
Tengo el móvil tal y como vino de fábrica pero con la actualización que sacaron poco después.
Un saludo.