Ubuntu 16.04 broken packages after fresh install

Question

After fresh install of Ubuntu 16.04, i have broken packages and can not install most of applications. I tried from Synaptic "Fix broken packages" but it is not working. An example;

sudo apt-get install steam

Output;

Reading package lists... Done
Building dependency tree       
Reading state information... Done
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:

The following packages have unmet dependencies:
 steam:i386 : Depends: libc6:i386 (>= 2.15) but it is not going to be    installed
          Depends: libstdc++6:i386 (>= 4.3) but it is not going to be installed
          Depends: libx11-6:i386 but it is not going to be installed
          Depends: libudev1:i386 but it is not going to be installed
          Depends: libxinerama1:i386 but it is not going to be installed
          Depends: libtxc-dxtn0:i386
          Depends: libgl1-mesa-dri:i386 but it is not going to be installed
          Depends: libgl1-mesa-glx:i386 but it is not going to be installed
E: Unable to correct problems, you have held broken packages.

An other example;

sudo apt-get install nvidia-361

Output;

Reading package lists... Done
Building dependency tree       
Reading state information... Done
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:

The following packages have unmet dependencies:
 nvidia-361 : Depends: lib32gcc1 but it is not going to be installed
              Depends: libc6-i386 but it is not going to be installed
E: Unable to correct problems, you have held broken packages.

There is no output from;

sudo apt-get clean

I tried;

sudo apt-get install -f

Outputs;

Reading package lists... Done
Building dependency tree       
Reading state information... Done
0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded.

Thanks..

Answer 1

16.04 is new and all packages are not ready to use in all servers. Using Main Server to download packages solve my problem.

1. System Settings
2. Software & Updates
3. Select "Main Server" from "Download from" section

Answer 2

I had the same issue after enabling foreign architecture for arm :

dpkg --print-foreign-architectures
i386
armvfp
armhf

This prevented apt update to complete fully, it always ended with :

N: Skipping acquire of configured file 'main/binary-armhf/Packages' as repository 'http://apt.llvm.org/xenial llvm-toolchain-xenial-3.9 InRelease' doesn't support architecture 'armhf'
N: Skipping acquire of configured file 'main/binary-armhf/Packages' as repository 'http://apt.llvm.org/xenial llvm-toolchain-xenial InRelease' doesn't support architecture 'armhf'
N: Skipping acquire of configured file 'non-free/binary-armhf/Packages' as repository 'http://repository.spotify.com stable InRelease' doesn't support architecture 'armhf'
W: http://ppa.launchpad.net/colingille/freshlight/ubuntu/dists/vivid/Release.gpg: Signature by key 3764AB961B292804CD3474FAEAE2E8E7CB7F5C71 uses weak digest algorithm (SHA1)
E: Failed to fetch http://us.archive.ubuntu.com/ubuntu/dists/xenial/main/binary-armhf/Packages  404  Not Found [IP: 91.189.91.23 80]
E: Failed to fetch http://security.ubuntu.com/ubuntu/dists/xenial-security/main/binary-armhf/Packages  404  Not Found [IP: 91.189.91.26 80]
E: Failed to fetch http://us.archive.ubuntu.com/ubuntu/dists/xenial-proposed/main/binary-armhf/Packages  404  Not Found [IP: 91.189.91.23 80]
E: Failed to fetch http://us.archive.ubuntu.com/ubuntu/dists/xenial-updates/main/binary-armhf/Packages  404  Not Found [IP: 91.189.91.23 80]
E: Some index files failed to download. They have been ignored, or old ones used instead.

While the errors were only for arm, it prevented to install many packages. Removing these architectures with sudo dpkg --remove-architecture armvfp and sudo dpkg --remove-architecture armhf followed by an apt update solved the issues.

I know the OP question is already answered, but the same symptoms happened in my case.