We're facing the same issue.
It seems to be related to the Jenkins CVS plugin (after updating from 1.2 to 2.7 which was a change from the commandline cvs client to the Netbeans Java API).
Comparing the output, it seems that now the plugin also uses "-r HEAD" for checkout / update:
cvs -q -z3 update -PdC -D "Friday, December 7, 2012 1:30:28 PM UTC"
cvs update -d -P -r HEAD -D 14 Jan 2013 10:33:16 +0100 workspace
Using the flag "Legacy Mode" changes the command to
cvs update -P -N -D 14 Jan 2013 12:22:23 +0100 <Module-path>
which seems to be a workaround.
I had a look at the cvs documentation, and there it is stated that -D and -r are exclusive or (so I think the new command with specifiying both isn't quite correct)