The problem is that Skype does not start when firewall is enabled. Or to be more specific - it only runs once after installing it.
Quick patch to fix the problem, thanks to this forum-post, is:
- Reinstall Skype
- Open Package Contents of the Skype.app in Finder
- In info-panes for Contents/Frameworks, Contents/MacOS and Contents/Resources, check "Locked"
- Enjoy your working Skype :)