I managed to reproduce it by stopping ntpd, setting the clock forward with "date -s" (rotation still working fine) and then back again. I guess running ntpd avoids the issue by ensuring the clock only increases monotonically.

xrandr (I cheated and just grabbed the debian package) also stops working so the bug isn't in the advanced backlight applet. I don't see anything clock-related in either the kernel or xserver patches either :-(

EDIT: I think this may explain it.

EDIT: Upstream bug, including patch. here.