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