I am trying to update a set of users with size 200. But some of them are not getting updated due to "Invalid Cross Reference ID" message. But when I change the batch size to 1, all of them are updated. Wonder why this happened?
This error normally means that an ID field referencing another object is invalid in the data.
If by "update a set of users" you mean the User SObject, that object contains self references such as "Manager" and so it is quite possible that a User early in the batch contains a reference to a User later in the batch (or a User in a later batch) and that will cause the update to fail. One way to work around this is to first load the data without the self references and then do a second pass to update the self references.
But this would only fit with your question if inadvertently during multiple upload attempts the later Users had been successfully inserted, giving the impression that the batch size was the key factor when it was not.