Comment 9 for bug 172651

This appears to be fixed since Hardy (screen 4.0.3-1):
    * Recreate /var/run/screen on install/reboot if necessary (e.g. tmpfs) with
      the appriopriate permissions (depending on the screen binary - some
      admins might choose to install it setuid using dpkg-statoverride).
      Closes: #357578, #390506, #397088.

I've run into this, because the init script link to /etc/init.d/screen-cleanup was missing on my system (accidently removed). I've solved this by reinstall screen:
sudo apt-get install --reinstall screen

The workaround seems to be manually extending the existing startup script, e.g. for Dapper or Gutsy with the snippet from Hardy for this:
case "$1" in
start)
    if test -L $SCREENDIR || ! test -d $SCREENDIR; then
        rm -f $SCREENDIR
        mkdir $SCREENDIR
        chown root:utmp $SCREENDIR
    fi
    find $SCREENDIR -type p -print0 | xargs -0r rm -f --
# If the local admin has used dpkg-statoverride to install screen setuid,
# change the permissions of $SCREENDIR accordingly
    if [ `stat -c%a /usr/bin/screen` -ge 4000 ]; then
        chmod 0755 $SCREENDIR
    else
        chmod 0775 $SCREENDIR
    fi
    ;;