Это обычно происходит из-за того, что вы не включили multiarch и обновили списки пакетов. Это может быть достигнуто легко:
sudo dpkg --add-architecture i386
sudo apt-get update
Первое говорит dpkg, что нам нравится поддерживать бинарные файлы i386 в нашей системе, APT запрашивает это и начинает загрузку не только списка пакетов amd64, но также i386. Я не уверен, почему это не дефолт в Ubuntu (в Debian это не так, но Debian поддерживает больше архитектур), но вот почему.