Getting citations and references right always requires multiple runs of latex. The normal procedure is the following
The first compile finds all the cite commands and makes a list of them in the .aux file, and takes note of the bibliography style. No citations are resolved in your document yet.
Then bibtex processes the aux file and using the bibliography style, and the list of citations creates a .bbl file which contains the bibliography. No citations are resolved yet here either.
The next latex compile doesn't resolve the references either, but reads the .bbl file and keeps track of the citations.
Finally the last latex compile resolves all the references.
The warnings you receive are normal, and should really only be paid attention to after the last latex compilation in the steps above.
There are various scripts that automate some of these procedures so that you don't forget to do the multiple latex runs; one is
latexmk and another is
Many text editors have access to these in some simple way, so before thinking about installing them you should find out if your editor already has a way to use them.