The reason is that there are x86_64 packages for applications like Skype, Crossover Office, etc that are in reality for the i386 architecture. Ubuntu does not know how to resolve the dependencies.
One solution is to use the i386 packages and try to let Ubuntu resolve the dependencies.
The second solution, which is the one I tried is to enable multiarch. And this is how it is done:
echo foreign-architecture i386 | sudo tee /etc/dpkg/dpkg.cfg.d/multiarch
Then install the required libraries for the i386 architecture:
sudo apt-get install libxss1:i386 libqtcore4:i386 libqt4-dbus:i386