This message means that a user who voted for one of your posts had their account deleted (either by request or due to violating the network's terms of service). As a result, all of their votes were removed, and the reputation you gained or lost from them was undone. The resultant reputation change could be any amount; it could even be a reputation gain if enough of the removed votes were downvotes. All the reputation changes from a single user's deletion are rolled into a single event in the reputation page labelled "User was removed".
We have a system in place that examines the impact of removing a user's votes. If the user has cast a large number of votes, deletion will be held up so staff may consider preserving the votes prior to the deletion. The decision is at the staff's discretion and cannot be reversed after the deletion has taken place. If you are seeing a "User was removed" event in your reputation history, it implies that the user either hadn't cast enough votes to be reviewed, or staff made the explicit decision not to preserve the votes.