So it’s just with date archives? My guess would have been your wordpress core got corrupted, but since you re-installed and this occurs with any theme, I can’t fathom what might be the problem… Sorry. Good luck, though.
PHP 5 vs. PHP 4?
Server issues; crazy PHP settings?
I’m no expert, just shooting in the dark.