Small addendum to the instructions above... I had to manually remove skype and skype-bin before dpkg would allow me to install the new version:
Code:
sudo dpkg -r skype
sudo dpkg -r skype-bin
And then, as per Moe's instructions,
Code:
sudo dpkg -i ~/Downloads/skype-ubuntu-precise_4.3.0.37-1_i386.deb
The new version did indeed fix the "Skype can't connect" problem; after a short "brought to you by your favorite intelligence agency" splash screen it connects without any hiccups.