I've been running leopard for a week. I enabled the firewall and rebooted the system and Skype stopped working. Reading the forums I found that this is a known problem with Skype on Leopard. If you have the firewall on, Skype stops functioning.
I downloaded a beta version of skype from here, and it seems to work fine for me.
Update: Skype beta is not working for me too.