Usually, these errors occur because the LaTeX compiler needs to run over the document more than once to get everything right, since it uses auxiliary files for keeping track of equations, citations etc.
If you're using BiBTeX, the recommended compile procedure is
pdflatex yourdocument.tex
bibtex yourdocument.aux (note the file ending)
pdflatex yourdocument.tex
pdflatex yourdocument.tex
but if you're not changing the order or location (within sections) of references, only a single run of pdflatex yourdocument.tex is usually necessary.
The reason for this is simply that pdflatex reads information from its auxiliary files on-the-fly, and at the same time updates them. Without running through this entire compile procedure, you can't be sure that all files are updated all the way until before the fourth step.