Hola amigo Xabato, yo tuve ese mismo problema y no lo pude solucionar, nunca supe la razon de porque no me dejaba usar esos programas, por ello lo desinstale, pero tengo unas recomendaciones, que son las comunes que te pueden servir en tu caso, aunque en el mio no funcionaron te las dire

En la ventana principal de sygate dirigete al menu y selecciona "Tools" y despues selecciona "Advanced Rules".

En la ventana que te salio haz click en "Add"

La ventana que sigue tiene 5 plantillas empecemos por el principio.

en la plantilla "General" en la parte de "Rule Description" pon Messenger es solo un nombre para poder identificar facilmente las reglas, despues haz click en la opcion "Allow This Traffic", en "Apply Rule to Network Interface" selecciona la opcion "all network interface cards", en "Apply This Rule during Screensaver Mode" selecciona "Both on and off", y la opcion "Record this traffic en packet log" dejalo en blanco(desmarcado).

Plantilla "Host" ten seleccionada la opcion "All Adresses" eso es todo en esta plantilla.

En la plantilla "Ports and Protocols", en la parte donde dice "Port" selecciona "TCP", en la parte donde dice Remote pon "1863,1503"(sin comillas muy importante), en Local no pongas nada y en "Traffic Direction" pon "outgoing".

Plantilla "Scheduling" no muevas nada.

Y en "Aplicattions" marca el MSN Messenger en recuadro con una palomita, despues das Aceptar.

Y si aun no te funciona con estos ocho pasos, prueba mi metodo alternativo:

Con esto deberia ser suficiente... pero apuesto que no sera asi, entonces puedes probar a desinstalar e instalar de nuevo el msn. si no te corre... has como hice yo... me rendi y desisntale el sygate.

OJO estas son recomendaciones muy personales, ya que yo tuve el mismo problema que tu y esas fueron las recomendaciones que yo recibi.. pero NO funcionaron

En fin, no deberias darte tantos dolores de cabezas, te desisntalas el sygate y listo, pruebas con otro firewall y pasas un feliz año nuevo