Why am I getting missing packages in Tex

The answer from Luís might not be for everyone since it requires to download a lot of packages that you might not need.

ulem.sty can actually be found in a much smaller package (3 MiB instead of 1 000 MiB), namely texlive-generic-recommended:

sudo apt-get install texlive-generic-recommended

Use the following command sequence:

sudo add-apt-repository ppa:texlive-backports/ppa
sudo apt-get update
sudo apt-get install texlive-full
        

This will get you the complete TeXLive package constellation. It is over 1 GB of stuff, but you will never worry with missing packages again. Both texlive and texlive-base provide only a subset of packages for the economy of space.