Replica of my post at http://forum.skype.com/index.php?showtopic=270961&view=findpost&p=1470111 with some screenshots
I'm using Ubuntu 8.10 Intrepid on Thinkpad R61 and I managed to get it work now (with Skype Test Call: echo123).
My problem started after installing Skype 2.0 for Linux. Skype reported "Audio Playback Problem" when I tried to make a call. This needs some adjustments before everything start working properly.
Solution: Go to Skype -> Options -> Sound Devices and Set Sound in/Sound out/Ringing to "pulse".
After this I can hear the voice from the other end of the line.
Next problem I encountered was: My voice didn't reach the other end.
Solution: It is something about Ubuntu "Capture" device, whose initial default is turned off and you can turn it on (for GNOME user) by: Go to Volume control preferences (Right click at speaker tray icon) -> Open Volume control -> Preferences -> Look for "Recording" devices (Mine are "Capture0" and "Capture1") and enable them and adjust the levels.
Another thing I manage to get the voice captured correctly is: Disabling "Allow Skype to automatically adjust my mixer levels"
Now my laptop can make a call properly. Hope this help.