Con App2SD es un apaño temporal, aunque creo que lo mejor es cambiar de rom en el móvil y tendrás todo el espacio de la SD disponible. A continuación te incluyo una pequeña de guía casera.

Bueno antes de empezar deberías hacer una copia de fotos, videos, docs y sms!! (que a mi se me olvido) al PC, los contactos solo tienes que exportarlos (es un archivo con todos) y luego los vuelves a importar, es lo mas fácil

Vale, a ver puedes empezar por aquí http://www.elandroidelibre.com/root que lo explican todo muy bien, en esa página explican muy bien el tema del rooteo, en el caso de HTC es el mas peculiar, yo lo hice así: http://www.elandroidelibre.com/2011/08/revolutionary-finalmente-trae-el-root-y-s-off-en-1-click-para-htc-desire-wildfire-sensation-evo-y-muchos-ms.html aunque hay otros sistemas como http://www.elalmacendelandroide.com/rootear-tu-android/root-htc-desire/

Después, deberás formatear la SD con una partición para apps con ext3.. para eso hay muchas aplicaciones, pero cuando rootes el movil el sistema de inicio que instala ya debería venir preparado y aquí tienes la guía http://www.htcmania.com/showthread.php?t=144195

Una vez echo eso solo tienes que elegir la rom y colocarla, normalmente en el raiz de la SD o con alguna app como esta http://www.elandroidelibre.com/2011/08/instala-roms-facilmente-con-rom-manager.html, nada mas intalar la rom deberás por supuesto bajarte el app2sd y otro para mover las caches a la SD que es lo realmente importante, yo utilizo el S2E (en el market) por que es el ideal para la rom de cyanogenmod que elegí, todas aquí: http://roms.htcmania.com/filtro.php?q=HTC%20Desire&e=Publicada&o=fecha_rom , aunque algunos mod traen incorporada la suya propia .

Es posible que el mod no traiga ni el market, ni gmail, ni nada de google, eso me pasó a mi, así que debes descargar un pack para instalarlo a parte... ahora no encuentro el enlace, pero con google sale fácil

Se que parece mucho lio, pero es muy sencillo, en serio.... solo que cada móvil tiene sus pasos por eso quizás hay mas lio. Y antes de empezar lee todo varias veces para decidir los pasos, rom, sistema de roteo, copias de seguridad, es bueno familiarizarse con el lenguaje y métodos, pero como te digo es sencillo, por cierto hacerte root no elimina tu sistema actual, solo modifica el arranque, por que se que hay apps que pueden cachear con el rom original de google, lo que pasa es que las de htc no valía, los mod son una gozada, te permiten una personalización que te cagas y accedes a aspectos de configuración de tu móvil que antes no podías... un ejemplo: http://www.elandroidelibre.com/2011/03/15-aplicaciones-imprescindibles-para-un-usuario-root.html