El problema con gdebi lo desconozco porque no lo uso, aunque
seguramente esté relacionado con el tema de Synaptic.
Con relación a Synaptic, el problema que me daba a mí (desde hace
aaaaaños) es que en XFCE no se inicia al ejecutarlo desde el menú, y si
no recuerdo mal, se debía a un problema de autentificación (polkit).
Si ese es tu problema, asegúrate de que tienes activado y se inicia el
demonio de policykit. Si tu problema es otro, especifica qué te sucede
exactamente :-)
P.S. Cuando te dé problemas alguna aplicación, ejecútala desde una
consola para ver si te saca algún error que te dé alguna pista.
Saludos,
--
Camaleón