Hi John,
What you should do it check your firewall configurations. Consult the Skype website as to what ports are needed. If your not sure how to fiddle with ports i sugget you read up at this site:
http://www.portforward.com/
Having said that Skype does suffer from significant audio delay and latency problems under particular circumstances.
Skype can become next to unusuable when having conversations with users in not so well connected countries, when users are not on a high bandwidth connection, and also when users had excessive processing power engaged by other simultaneously running applications.
There are other SOHO VoIP tools which are outstandingly better than Skype in terms of quality, reliability, latency and ability to work on any type of connection line, from 14.4 Kbps and up. Anyone who asserts to the contrary has not been telling you the truth.
If your problems persit on Skype, and your sure that your setup correctly why not try one of the many other provders out there?
Hope this helps.
Matt :D