Comment 21 for bug 1117292

This happens to me, too, server installation is currently broken in some settings. This appears to be a bug or a race in the installer logic, as running the apt-get command by hand in a chroot succeeded. So apparently there is not really an error during the underlying package installation, just the installer got confused.

As a workaround I have installed 12.04 server (which installed just fine), and then upgraded to 14.04. Not pretty, but at least that worked.