I'm trying to run pkg_rolling-replace for the first time.  It worked
  fine for the 50-or-so packages, but then I get this persistent error
  for each package it tries to install:

pkg_rolling-replace really just runs 'make clean;make replace package
clean' in the right order.  So while you are having trouble with
pkg_rolling-replace, I think you are likely really having trouble with
make replace.  I often find that on a system which has had pkgsrc for a
long time there are things wrong in /var/db/pkg and the first run of
pkg_rr is hard, and then there is little trouble.

  => Becoming ``root'' to make su-replace (sudo)
  Creating binary package: p5-perl-headers-4.99.12nb3
  Creating package /objs/pkgsrc/devel/p5-perl-headers/work/p5-perl-headers-4.99.12nb3
  Registering depends: perl>=5.8.7.
  Registering conflicts:.
  => Preserving existing +INSTALLED_INFO file.
  => Preserving existing +REQUIRED_BY file.

  mv: rename /objs/pkgsrc/devel/p5-perl-headers/work/.replace-+REQUIRED_BY to /var/db/pkg/p5-perl-headers-4.99.35nb3/+REQUIRED_BY: No such file or directory

In this case, it looks like the install step was skipped.

Are you sure that you have no work directories before you start?

I did just change the make replace logic to allow replacing a different
package than the one that was installed, but I've been running pkg_rr on
several systems since then without trouble.

Can you clean out all workdirs, and then "pkg_rolling-replace -uvn" and
save that, and then try to do 'make replace package clean' as root in
the first package?

I am remembering that make replace seems to not work right when run as a
normal user.  That is probably the problem here.