I am experiencing this problem for the first time with Ubuntu 16.04, after a fresh installation.
Skype cannot be located after enabling Canonical Partners both in Software & Update, or by command line with the command:
sudo add-apt-repository "deb http://archive.canonical.com/ $(lsb_release -sc) partner"
Then running the following:
sudo apt-get update
sudo apt-get install skype
However, I still get:
E: Unable to locate package skype
Any clue?
UPDATE
I run "sudo apt-get update --fix-missing" before trying to install skype, and this is the output I get:
Hit:1 http://cran.rstudio.com/bin/linux/ubuntu xenial/ InRelease
Hit:2 http://archive.canonical.com/ubuntu xenial InRelease
Hit:3 http://id.archive.ubuntu.com/ubuntu xenial InRelease
Get:4 http://security.ubuntu.com/ubuntu xenial-security InRelease [102 kB]
Get:5 http://id.archive.ubuntu.com/ubuntu xenial-updates InRelease [102 kB]
Get:6 http://id.archive.ubuntu.com/ubuntu xenial-backports InRelease [102 kB]
Fetched 306 kB in 3s (79.5 kB/s)
Reading package lists... Done
I try "sudo apt-get install skype" again, and I obtain:
Reading package lists... Done
Building dependency tree
Reading state information... Done
E: Unable to locate package skype
The legacy Skype for Linux application was discontinued and removed from Canonical's partner repositories. You can install the new Skype for Linux application instead.
I've installed recently this way:
Add Skype repo
Add i386 architecture
DaniCee!
I think I have a solution for your problem. Of course, there's the terminal way which hasn't worked for you, but I'll put here for redundancy's sake.
Now that we've covered option 1, your second option is to simply search in Synaptic. Make sure it's "skype" with a lowercase s, and not "Skype" with an uppercase S. I was able to find it in Synaptic, but that may be because I have Skype installed already.
Finally, you can simply to this website https://www.skype.com/en/download-skype/skype-for-linux/ and click the download .deb option and voila! skype.deb is now available to download manually (is that considered manual?). Hope this helps out!