Okay, if anyone is looking for a tough genealogy problem to solve, here it is:

Puzzle Piece #1:

My grandfather's name is Leon Eugene Barber. His father is named Alden Burt Barber. Leon has a brother, Harold, and a sister, Anna. Leon was born in Batavia, Genesee County, New York. This is all proved by the following sources:

1900 US Federal Census, connecting the family unit.
1910 US Federal Census, connecting the family unit.
Leon's WWI US Navy death records, indicating parentage of Alden to Leon.
The fact their graves are in the same, Fairmount Cemetery, in Signal Mountain, TN
I feel like these facts are pretty solid.

Puzzle Piece #2:

The father of Alden Burt Barber is named, Henry Barber. Alden has sister named Kate. Sources for Alden are as follows:

Death certificate for Alden lists Leon as the Informant and Henry as the father of Alden.
1860 US Federal Census lists "Henry Barber" as the head, "Lucy A Barber" as the wife and Kate and Burt as the children. All living in Batavia, Genesee County, NY.
1870 US Federal Census lists "H. R. Barber" as the head, Lucia as the "wife" and Kate and Burt as children. All living in Batavia, Genesee County, NY.
1880 US Federal Census list "Henry R. Barber" married to "Lucy A Barber" and living in Darien, also in Genesee County, NY. Looks like the kids had moved out, which matches up with the belief that they all moved south, at this point.
I think we're still on firm ground here.

Puzzle Piece #3:

Here's where the puzzle is missing a piece or two. There is a gravestone in Batavia Cemetery for a "Henry R. Barber." All the sources listed above, for Henry, have an approximate date of birth as 1826 or 1827. We'll say 1826. This date matches what is on the gravestone in Batavia Cemetery. There is also a gravestone in Riverside Cemetery in Plattsburgh, Clinton County, NY. The stone seems to be a family stone and has the name, Henry Ransom Barber, along with all of his siblings and parents. The birth date, for Henry Ransom Barber, on this gravestone, is "1839."

Now, it has been and is widely believed, by my family and others, that this "Henry Ransom Barber", in Riverside Cemetery, is the Henry referred to in Puzzle Piece #2 above. The reasons I DON'T believe this are as follows:

Not considering the two separate gravestones, the birth dates are too far off and the numbers too different for this to be typo within written records.
There are, in fact, two different gravestones in two different cemeteries. This must be two different people.
The birth date for Henry R. Barber, in Batavia Cemetery, NOT Henry Ransom Barber, matches the approximate birth date listed in the census sources above (1826).
The gravestone, for Henry R. Barber, not Henry Ransom Barber, is located in a cemetery within the same town as the sources above (Batavia).
My conclusion is that "Henry R. Barber" in Batavia Cemetery, born in approximately 1826, is my ancestor, not Henry Ransom Barber, in Riverside Cemetery.

Puzzle Piece #4:

Assuming I am correct about my conclusion about Henry R. Barber, all I know about him is the following:

He is buried in Batavia Cemetery, Batavia, Genesee County, New York.
The census record, from the 1880 Census above, lists his father as being from Vermont
There is an obituary which names his daughter, "Mrs. S. E. Spaulding", his son, "Burt Barber" and a brother "Carlos M. Barber." This obituary is from the March 15, 1898, edition of The Daily News, in Batavia.
The death date, listed in this obituary, matches the gravestone in Batavia Cemetery.
There is a gravestone for a Daniel Barber and an Anna Barber, in Batavia Cemetery. Both have dates on them that might suggest possible parentage of Henry.
Problems halting my research:

I cannot find a birth record for Henry R. Barber, though census records and the gravestone indicate he was born in New York, around 1826.
I cannot find records, definitively, connecting Henry to parents of any kind. I only know his father was from Vermont.
I cannot find records connecting Henry to Carlos or a sister, other than the obituary.
Investigation of Daniel and/or Anna, listed above, as potential parents of Henry, yielded nothing.