I've got an Ubuntu (9.04/Jaunty) server VPS that's not properly rotating syslogs.
Here's what I've checked so far:
- syslogd-listfiles lists the files I think should be rotated
 - cron.daily is running (so sayeth syslog)
 - when I manually run the file checks at the beginning of /etc/cron.daily/sysklogd they all pass (
test -x /usr/sbin/syslogd-listfiles,test -x /sbin/syslogd,test -f /usr/share/sysklogd/dummy) - when I run the cron.daily job manually as root (
sudo run-parts --verbose /etc/cron.daily) the logs rotate as I would expect 
Anybody have any ideas what I might try next or what I might be missing?  I was thinking that perhaps the fact that sysklogd seems to be running it's process as syslog (the owner of the syslogd per ps -C syslogd -o user= | head -n 1) means that there's some sort of permissions issue, and that seems to be supported by the results of running sudo -u syslog run-parts --verbose /etc/cron.daily which ends up with a bunch of permissions erros, but I'm not sure what the best way to resolve that would be.
Contents of my sysklogd file follow, in case that's of assistance. The touch /etc/crontouchtest bit is something I inserted to verify when the file is run successfully.  It updates the last used time (ls -lut /etc/crontouchtest) when I execute the run-parts as root, but not when the cron.daily runs.
#! /bin/sh
# sysklogd      Cron script to rotate system log files daily.
#
#               If you want to rotate other logfiles daily, edit
#               this script.  An easy way is to add files manually,
#               to add -a (for all log files) to syslogd-listfiles and
#               add some grep stuff, or use the -s pattern argument to
#               specify files that must not be listed.
#
#               This is a configration file.  You are invited to edit
#               it and maintain it on your own.  You'll have to do
#               that if you don't like the default policy
#               wrt. rotating logfiles (i.e. with large logfiles
#               weekly and daily rotation may interfere).  If you edit
#               this file and don't let dpkg upgrade it, you have full
#               control over it.  Please read the manpage to
#               syslogd-listfiles.
#
#               Written by Martin Schulze <joey@debian.org>.
#               $Id: cron.daily,v 1.14 2007-05-28 16:33:34 joey Exp $
test -x /usr/sbin/syslogd-listfiles || exit 0
test -x /sbin/syslogd || exit 0
test -f /usr/share/sysklogd/dummy || exit 0
touch /etc/crontouchtest
USER=$(ps -C syslogd -o user= | head -n 1)
[ -z "${USER}" ] && USER="root" || true
set -e
cd /var/log
logs=$(syslogd-listfiles)
test -n "$logs" || exit 0
for LOG in $logs
do
   if [ -s $LOG ]; then
      savelog -g adm -m 640 -u ${USER} -c 7 $LOG >/dev/null
   fi
done
# Restart syslogd
#
/etc/init.d/sysklogd reload-or-restart > /dev/null
EDIT
Outputs as requested:
ls -la /etc/cron.daily (run as root)
drwxr-xr-x   2 root root 4096 Oct 23 07:13 .
drwxr-xr-x 107 root root 4096 Oct 23 07:14 ..
-rwxr-xr-x   1 root root  314 Feb 10  2009 aptitude
-rwxr-xr-x   1 root root  111 May 11 11:49 backup-manager
-rwxr-xr-x   1 root root   89 Jan 26  2009 logrotate
-rwxr-xr-x   1 root root 1334 Oct 22 09:35 sysklogd
ps -ef | egrep '[c]ron' (run as root)
root     13369     1  0 Oct21 ?        00:00:02 /usr/sbin/cron
EDIT 2
Respective paths
from echo $PATH (after swithcing to root):
/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/games
from /etc/crontab:
PATH=/usr/local/sbin:/usr/local/bin:/sbin:/bin:/usr/sbin:/usr/bin