Tienes todos los repositorios actualizados? Si no es así o no sabes de que te estoy hablando podrías pasarte por aqui:
http://easyurpmi.zarb.org/ y seguir las instrucciones para actualizarlos.
No se me ocurre otra cosa, esta vez no te dice que la versión de perl-unicode-string es demasiado antigua?
No sé, prueba eso y sino a ver si se nos ocurre alguna otra cosa. Suerte, siento no poder ayudar mucho más