Not using Endian at the moment, but familiar with Smoothwall.
Open any outgoing port, eg 45000, and allow for bidirectional traffic on that port.
In Skype (v4.0.0.x) go to Tools - Options - Advanced - Connection
In the first block, where it says "Use port xxxx for incoming connections", change that value to 45000 and see if that will help.
Leave the rest of the settings as is.
HTH
Libs
Yes... and no. Skype lets you choose an incoming port, but this cannot be used as a rule in endian. Endian doesn't let you create rules by incoming port, only by outgoing.
I made a change to allow rules by incoming port, but this means tweaking the EFW (so its not vanilla anymore).
Maybe you can try to enable ports 80 & 443 in Skype, also try to log the traffic and check what packets are being blocked for the computer with the Skype.
Skype is a hell for Firewalls. You cannot exactly allow it nor deny it (as MSN Messenger for example), it uses P2P theory and bad practices to connect (UDP hole punching, trasversal NAT, etc... see this old paper
http://www1.cs.columbia.edu/~library/TR-repository/reports/reports-2004/cucs-039-04.pdf).
So it forces you to create bad rules in the firewall.