As Predrag found in alice.cern.ch, the CVMFS server fails when directory entries are removed and the parent directory is renamed in the same transaction. Example with a repository containing foo/v1.0:
At first glance this happens because the rm -fR foo/v1.0 creates a whiteout file in foo. Afterwards mv foo FOO does an up-copy of the entire foo directory into FOO (including the whiteout for foo/v1.0) and creates a whiteout for foo in the root directory.
CVMFS treats foo to be removed entirely and FOO to be a completely new directory. Both cases will result in a full recursive traversal removing respectively adding all entries found in there. The latter hits the (now probably useless) whiteout for foo/v1.0 which it cannot read and crashes.
The above is an educated guess and up for further investigation...