I was trying to update all my packages via pkg_rolling-replace
  -rsux sudo and this failed with:

  ===> Deinstalling for png-1.2.19
  Running /usr/sbin/pkg_delete -K /var/db/pkg  png-1.2.18
  => Required installed package digest>=20010302: digest-20070803 found
  => Required installed package checkperms>=1.1: checkperms-1.7 found
  => Fixing @pkgdep entries in dependent packages.
  mv: rename /storage/pkgsrc-obj/graphics/png/work/.replace-+REQUIRED_BY
  to /var/db/pkg/png-1.2.19/+REQUIRED_BY: No such file or directory *** Error
  code 1

  png is now removed, I'm using latest remove and pkg_install from:

  $ pkg_add -V
  20070821
  $

There has been various trouble with make replace.  I think that when it
invokes sudo to operate, as opposed to being run as root, it doesn't
work.

It would be helpful to check if mv is complaining about the lack of
.replace-+REQUIRED_BY or if the png-1.2.19 directory.

Are you sure that you are running updated head pkgsrc, or are you on a
branch?

See /usr/pkgsrc/mk/flavor/pkg/replace.mk for how this happens.