Looks like tuberculosis may have been a human affliction for far longer than previously thought:

Molecular analysis suggests that the East African samples and the commoner strains are all descended from a more ancient bacterial species that emerged in Africa as long as three million years ago.

Of course, being descended from and being made ill from are two different things. Considering that TB is a disease that leaves major indicators of its presence in bones, I find it a bit surprising we haven't found any evidence of it in the fossil record. Then again, considering how rare post-cranial human fossils are, it's quite possible our sample size isn't big enough to find anything.