Could be your microphone (impedance). Try another one if you have.
Having used different types of microphone eg dynamic and electret I never
had your type of problem.
I trust your loudspeakers/headphones are OK ,meaning the sound quality of
the speech by the ' Skype test lady' is OK.

Skype lady sounds fine. I sound like a 60's smog on London Bridge. I think I
have another mike and some speakers somewhere, I'll try that - thanks.

I do not use it on Ubuntu but on Windows 7 its as clear as a bell for me..