Latex can't find .sty files altough packages are installed -- TexLive, Ubuntu 12.04

First suggestion would be, Check if the caption.sty file is somewhere on the system

$ locate caption.sty

If it is not installed, most probably the package is not on the basic configuration of texlive.

I used the command

$ apt-cache search caption | grep tex

and found the following packages

texlive-latex-recommended - TeX Live: LaTeX recommended packages
texlive-pictures - TeX Live: Graphics, pictures, diagrams
texlive-latex-extra - TeX Live: LaTeX additional packages
telxcc - Teletext closed captioning decoder

Install them,

$ sudo apt-get -y install texlive-latex-recommended texlive-pictures texlive-latex-extra

and try compiling again!

Friendly advise

If you have hard disk space to spare, I would recommend to install texlive-full, which contains all the packages of the texlive version on the repository. So you have less chance to have this type of problems.

If you install manually

Make sure you add the following lines to your ~/.bashrc file

PATH=$PATH:/usr/local/texlive/2013/bin/x86_64-linux
export PATH
MANPATH=$MANPATH:/usr/local/texlive/2013/texmf/doc/man
export MANPATH
INFOPATH=$INFOPATH:/usr/local/texlive/2013/texmf/doc/info
export INFOPATH

Cheers.