Steven,

Just wanted to be sure that these records are your family :

COLE, HENRY ANDERSON, MARTHA 1841-03-03 00B/0174 LAWRENCE
Illinois Statewide Marriage Index, 1763–1900

Henry Cole 40 VA
Martha Cole 26 IL
David Cole 10 IL
Jacob Cole 3 IL
Dicy Ann Cole 1 IL
Year: 1850; Census Place: , Lawrence, Illinois;
Roll M432_115; Page: 54A;

Henry Cole 57 VA
Martha Cole 36 IL
David Cole 17 IL
Jacob Cole 13 IL
Robert Cole 9 IL
Thomas Cole 8 IN
Wm Cole 3 IN
Benj Cole 8/12 IN
Year: 1860; Census Place: White River, Gibson, Indiana;
Roll M653_260; Page: 863; Image: 353;
Family History Library Film: 803260.

Henry Cole 75 TN
Martha Cole 45 IL
David Cole 23 IL
Thomas Cole 15 IN
Benjamin Cole 11 IN
Isaac Cole 7 IN
Rose Anderson 15 IL
Jacob Cole 23 IL
Ahmina Cole 18 IN (Almira)
Louisa Cole 4/12 IN
Year: 1870; Census Place: White River, Gibson, Indiana;
Roll M593_316; Page: 364A; Image: 731;
Family History Library Film: 545815.

Personally, I'd be hoping that he was born in VA because TN just doesn't that many good records for that period.

Ron