Skype doesn't have a release for 64-bit Ubuntu distributions. I'm running Ubuntu Feisty fawn that's Ubuntu 7.04. The .deb from the Skype for Linux download page doesn't work on a 64-bit architecture.

Here's some documentation on how to work around it.

The fix didn't work for me though :( All I got after installing was a "/usr/sbin/skype doesn't exist"