The 6509 is not showing timestamps on its logs. It shows the uptime instead.
"service timestamps log datetime localtime" is set. The same goes for debug.
The clock is set on UTC from an NTP server (per policy). Should this make a difference? If not, then what am I missing?
I saw "set logging timestamps" command for 6500 series, but that doesn't work on this IOS version (12.2 (18)), I suppose.
Have you tried without the 'localtime' option in the service timestamps log? My guess would be the 'clock timezone' might be required for the localtime option to work and its absense is causing issues.