ia32-libs

Android is full of 32-bit tools and dependencies.
Running on x64 can be problematic unless you install ia32-libs.
Unfortunately, Ubuntu has been having issues installing it lately.

After 2 days, I finally found the solution here:

sudo dpkg --add-architecture i386
sudo apt-get update
sudo apt-get install ia32-libs

After that, everything installs fine.