First off, let's dispense with making "date" and "time" two separate things. A date is just a way to express longer times, so there's no need for it. Let's just call it "time". After all, the year 1532 is a "time", but 8:00 this morning is not a "date", so "time" is the better descriptor.
Now let's think of a data structure. An unsigned 64-bit integer is capable of holding millionths of a second for about 585,000 years, so let's go with that. That'll satisfy the game-geeks who need millisecond timing along with the epoch counters who want to know what day of the week was July 4, 1776. We can even extend the calendar back a few thousand years. Let's make our pivot-point the date of the moon-landing (certainly a significant date, and much closer and easier to pinpoint than any ancient religious events), so our date object will be able to cover millionths of a second from approx 290,502 BCE to 294,440 CE. So you'll be able to use this time-object to track the journey of early protohumans across the Siberian landbridge, but you won't be able to track the progress of the Eloi and the Morlocks. Still, it's a good range and resolution.
. . .and Eloi and Morlocks weren't real anyway.
I mentioned before that this Ultimate Time Class of the Universe is probably entirely unworkable, and now's where it gets hairy. While it's got excellent resolution and range and not-unreasonable size (8 bytes ain't bad for computers today), the math necessary to calculate anything would be frighteningly ugly. To convert a 64-bit integer of microseconds into a "Tuesday February 24, 2004, 3:51 PM CST" would require some seriously ugly math, especially taking into account the little games that mankind's been playing with time ever since. . .well. . .time began. Things like adding or subtracting "leap seconds" now and then, and the Gregorian Calendar Reformations (when Pope Gregory III in 1582 declared that the day after October 4 would be October 15 to get the calendar back in sync with astronomy).
Maybe it won't be too ugly. Here's the code from my original date class that converts a month, day, and year into a Julian date (number of days since Jan 1, 5713 BCE). You'd think it'd be pretty hairy too, but it's not bad.
void Date::DMY(const ui8 &rDay, const ui8 &rMonth, const ui16 &rYear)
if (MonthToUse <= 2)
MonthToUse += 12;
i16 a = YearToUse/100;
nDate = (ui16)((i32)(365.25*YearToUse) + (i32)(30.6001*(MonthToUse+1)) + rDay + 1720994L + (2 - a + a/4));
Oh, and for those who don't care about any of this, July 4, 1776 was a Thursday. Now you know something new.