I was having issues with Skype today and searched for this old article by Paul O'Flaherty http://pauloflaherty.com/2008/03/26/improve-skype-quality-with-these-tips/

                                                                                                        

1. In Skype, Go to Tools > Options > Connection. Select the option to use ports 80 and 443. In the “Incoming Connections” box you can chose any port between 1024 and 65535.

2. Reconfirm that your firewall is correctly configured. Follow the simple visual guide here:

http://www.skype.com/help/guides/firewalls/

3. Quit any file sharing applications or high-bandwidth usage applications.

4. For more detailed security setup on a network: http://www.skype.com/security/guide-for-network-admins.pdf

5. If these suggestions do not resolve improve call quality, follow these steps:

* Quit Skype

* Locate the shared.xml file found in
C:\Documents and settings\Your Windows Username\Application data\Skype\shared.xml

* Delete the file called shared.xml

* Restart Skype ( shared.xml will be recreated )
Note: Showing hidden folders and files has to be turned on: please navigate to :

In XP – My Computer > Tools (Menu) > Folder Options > View.

In Windows 7 – Open Explorer >Organize (Menu)> Folder And Search Options > View.

Once there, please make sure that the option “Show Hidden Files and Folders” is enabled.

6. Disable Quality of Service packet scheduling. Go to Start -> Control Panel -> Network Connections.  Right click on the connection you are using. Select Properties. Untick the “QoS Packet Scheduler” option.

I just do step 5. I don't delete shared.xml, I just append it with a 1. I remember having done this as a maintenance activity back in the day from time to time whenever I had issues with Skype and it seemed to work every time.

HTH.