I would try to trace with access-deny option selected. I would also check if the Role-to-object coupled to your access group as sufficent access to the class of interest. You could move Role-to-objects from your other user to see which one gives them the appropriate access and then review the deltas.
Was this resolved using rowlandstilwell_gcs 's suggestion? I am asking because I am getting the same error now after deleting a case that was completely messed up. I cannot figure out how to resolve this. Any help would be appreciated.