People did change names--I know of two men in my tree who switched names, and one woman who claimed to be married to a man for a short while, so she could use his name instead of her previous name.
When searching for birth records, remember that it depends on location. A large, well established city will be more likely to have kept track of births than a small, out of the way village. Also, in addition to searching through civil records, also search through church records. In New Mexico, for example, a researcher will have better luck (than with civil records) if their family is Catholic. This is because the Catholic records there extend through governance by the U.S. as a state, as a territory, as a Mexican Territory and as a Province and Kingdom of Spain. By searching Catholic records, a researcher can more easily find answers.
This might not be true in all cases, but church records are a good resource.
