Hola murderslon!
Comentas:
Por supuesto he probado utilizando 3 fuentes: 5 V, 12 V y 9 V (con una pila), y todo funciona perfectamente, el problema es que no puedo usar esa pila
Eso significa que lo que necesitabas ya lo has conseguido (y funciona), pues bien, como diseñaríamos la fuente? (y que esta fuera lo más inmune al ruido, o lo que quiera que ocurra en tú circuito).
Yo soy un poco bruto, primero me gusta hacer que funcione y después perfecciono (o no, depende del tiempo que tenga

).
Yo buscaría un trafo con 3 secundarios. A cada secundario le pondría su correspondiente puente rectificador, condensador de 220uF, condensador de 100nF, regulador, Condensador de 10uF, Condensador de 100nF.
De esta forma (al igual que con la pila te funcionaba) tendría que funcionar.
El dibujillo de la fuente que nos has puesto a mi me da un poco de mal rollo. Tienes los tres reguladores enganchados al mismo secundario y... cuando se produzca una demanda de corriente brusca en alguno de ellos seguro que los otros 2 también sufren.
Con 3 secundarios y tres reguladores (uno en cada secundario) se podría descartar si es ese el problema.
Si ves viable esta prueba hazla y nos cuentas. Si es demasiado follón, avísanos para que te podamos dar más ideas.
Por cierto, lo que dice elmasvital es importantísimo. Que no se te olvide el condensador de desacoplo. Yo soy un poco paranoico y me gusta poner uno de 10uF y otro de 100nF, muy juntitos a las patillas del PIC (tengo diseños que si pongo sólo el de 100nF se me reinician y que cuando le añado el de 10uF todo va a las 1000 maravillas).
Bueno, esperamos noticias.
PD: También tienes que tener en cuenta el fuse 'BROWNOUT'. Esto te resetea el pic cuando detecta un bajón en la alimentación. Para hacer las pruebas te recomendaría que lo quitaras (NOBROWNOUT), pero, que antes de dar el diseño por finalizado lo actives. Yo considero un suicidio hacer un equipo con esto desactivado, ¿por que? Pues... si tienes un micro-bajón en la alimentación del pic y este no se reinicia, el funcionamiento del programa puede ser errático (me lo dice la experiencia, que no es mucha pero bueno... jeje).
Un saludo desde Alicante.