libxml-dev
foi o último visto em Hardy - então, se você definitivamente ainda precisa deste pacote, você poderia tentar baixar o deb apropriado para sua plataforma e instalar isso.
libxml2-dev
está disponível no centro de software ou no synaptic.