In a comment on Tom Evslin's post on SkypeOut, Edward Vielmetti notes "some really bad artifacts calling out from SkypeOut through the PSTN into someone else's VOIP phone, enough to make the call too poor quality to carry on a business conversation."
Skype uses the Global IP Sound iSAC codec for Skype-to-Skype calls, but uses G.729a for SkypeOut calls. Most VoIP providers use G.711.
Various reports (sorry, no links I can find) indicate G.729a gives a Mean Opinion Score (MOS) in the range of 3.75 to 4.0, which is perfectly acceptable. G.711 MOS is generally between 4.1 and 4.5. However, serial coding (G.729a to G.711) generally drops the MOS between 0.5 and 0.75 points.
Not knowing details about Skype's implementation of the G.729a codec or the circuit gateway they're using, it's hard to say more.