Skype on Linux comes with it’s own notification system. It’s not that bad, but it’s not consistent, either. If you want to configure Skype to use libnotify instead, run the following script in your terminal:

(NOTE: You must have installed Skype, and logged in at least once.)

bash < <(curl -s https://raw.github.com/gist/2181122/skype-libnotify.sh)

This downloads and executes the script from this gist: https://gist.github.com/2181122

It fetches the skype configuration from here, which is part of my dotfiles repo.