Okay, I've been dealing with this problem FOREVER. On one box, my syslog-ng server, logrotate consumes 100% CPU for several hours, but will eventually finish. For this whole time, I've been thinking it's a bad logrotate script, but I've never been able to isolate it. My recent attempt to isolate the problem, I used strace to see what was going on.
strace -o mytrace -fF /usr/sbin/logrotate -d /etc/logrotate.confI immediately saw it looping on /etc/localtime. Here is a partial output of my strace:

Recent comments
37 weeks 6 days ago
38 weeks 4 days ago
42 weeks 5 hours ago
42 weeks 5 hours ago
1 year 6 weeks ago
1 year 14 weeks ago
1 year 21 weeks ago
1 year 25 weeks ago
1 year 32 weeks ago
1 year 32 weeks ago