I have the same problem as described in the questions skype notification sounds sizzled and bad sound on login to skype. But it is not only the login, notification, but also when talking to somebody. I tried the solution to remove/re-install skype and most of the solutions in this questions, e.g. checking mixer, sound settings and installing alsa-hda-dkms (incl. system restart).
After installing skype (and even after upgrade to skype 4.0) in Ubuntu 12.04 (AMD 64) there was no sound at all. I followed the first step of the SoundTroubleshootingProcedure and at least there is now sound:

sudo add-apt-repository ppa:ubuntu-audio-dev/ppa; sudo apt-get update;sudo apt-get dist-upgrade; sudo apt-get install linux-sound-base alsa-base alsa-utils gdm ubuntu-desktop  linux-image-`uname -r` libasound2; sudo apt-get -y --reinstall install linux-sound-base alsa-base alsa-utils gdm ubuntu-desktop  linux-image-`uname -r` libasound2; killall pulseaudio; rm -r ~/.pulse*; sudo usermod -aG `cat /etc/group | grep -e '^pulse:' -e '^audio:' -e '^pulse-access:' -e '^pulse-rt:' -e '^video:' | awk -F: '{print $1}' | tr '\n' ',' | sed 's:,$::g'` `whoami`

The jittering sound would sometimes disappear, e.g. on the Echo-Testcall after replaying the recorded part. And I noticed that if I let music play in the rhythmbox and then start skype, the sound is fine. So I have a weak solution, but I would be glad it would work without this detour.

As requested: My sound card is a an "AMD High Definition Audio Device" called Advanced Micro Devices (AMD) Hudson Azalia controller (rev01), subsystem Lenovo Device 21ea (according to sysinfo) on a Lenovo Thinkpad Edge 525.