There are two main important comments in here:
- what information loss means is a bit more technical than the examples you provided (it is not a matter of information falling down the black hole, and burning a book preserves information);
- it is not a consensus that black hole information loss is a paradox or a problem. (I'll provide references published in reputable journals of scientists with a different point of view)
In this answer, I'll try to briefly explain what the "problem" is and why someone could be bothered by it (or at least I'll try, since I am not bothered by it). In particular, I'll try to focus on how it is different than the situations you gave as examples. Next, I'll give some reasons to why there are scientists who believe it is not a problem at all.
What black hole information loss is not
To say what the problem is, let me begin by saying what it is not. The example of matter falling into a black hole does not constitute an example of information loss. Of course, you can't see the information from outside the black hole, but there is no reason in principle to believe it is not there. The key difference is that if, somehow, one had all of the information on the universe (including inside black holes) at a fixed time, then one would be able to compute the past and future history of everything in the universe. In this sense, information is being preserved: one can compute all of the data at any time by having access to the data at a given time.
It should be pointed out that, in General Relativity, it is difficult to define what one means by "at a fixed time", for time is relative.
A second example of what information loss is not is, as mentioned by other people, burning a book. While the information in the book is now is an extremely messy state, one could, in principle, rebuild the book from its ashes and from the thermal radiation emitted in the burning process. In practice, it is difficult to do this, but the point is: if you have all the information (positions, velocities, etc) available in the Universe at time $t$, you can obtain all of the information for any other time $t'$.
What black hole information loss is
The tricky bit with black holes comes when quantum effects are taken into consideration. As far as we know, quantum effects imply that black holes emit radiation, which is known as the Hawking effect. As the black hole emits radiation, it loses energy. In Relativity, mass and energy are essentially the same thing (that is the meaning of the famous equation $E = mc^2$), so the black hole is losing mass. As it loses mass, it "evaporates". If you trust the calculations made by Hawking in the 1970's until the end of the evaporation process, the black hole will vanish within a finite time. Remark: these calculations might not be trustworthy, but one might then start asking where they could fail. I'll discuss this later on.
Now things get weird: suppose you had a star made of matter (as opposed to antimatter) collapse into a black hole. There is a result in General Relativity, known as the no-hair theorem, that states that all of the properties that characterize a black hole from the outside are its mass, charge, and spin (I'm overlooking technical details, but this is essentially the idea). Hence, it doesn't matter if the black hole was created out of a star made of matter or antimatter.
So far so good. If we somehow could get the information inside the black hole, we could in principle know that the star was made of matter and hence compute that the black hole was created out of a star made of matter. No information has been lost.
So far.
The problem is that nasty quantum effect: Hawking radiation means the black hole will evaporate. Once it does, where did the information regarding the star go? All of the information that remained was the black hole's mass, charge, and spin (the only data available from the outside) and everything on the inside vanished. If we try to pick data after the black hole vanish, we won't be able to compute what the star was made of before it collapsed. In this sense, information has been lost.
Why is this a problem?
Some physicists see this as a problem, and often call this conclusion "the black hole information loss paradox". The reason is that in their point of view, quantum mechanics ought to be "unitary", which is jargon for saying information loss can't happen. They understand that this prediction is in conflict with the basis of quantum mechanics and hence is problematic. This has led to a number of studies trying to "solve" the paradox, often in the context of quantum gravity (i.e., by trying to find a way to bypass Hawking's computations in a regime where we no longer trust them).
In a bit more technical manner,
Thus, semiclassically, an initial pure state will evolve to a mixed state. For reasons I have not been able to understand during the course of the past 40 years, this is widely viewed as being highly problematic. The conflict between this view and the semiclassical analysis is referred to as the black hole information loss paradox.
as was put by Robert Wald in this 2019 paper. I agree with the points made by Wald in both this paper and in the one I'll mention in the next section. Hence, I'm not bothered by the "paradox" and, as a consequence, I can't provide much more detail into why someone would be bothered by this. In short, the thing is "Some scientists believe the result disagrees with basic concepts of quantum mechanics". Some notorious scientists with this view are, if I'm not mistaken, Leonard Susskind and Gerardus 't Hooft.
Why is this not a problem?
The other view is that it is not a problem. A direct argument for that could be, for example, that apparently unnecessary and innocent comment I made a few paragraphs ago: "in General Relativity, it is difficult to define what one means by 'at a fixed time', for time is relative". For you to be able to define what you mean by "constant time", you'd need your spacetime to satisfy some technical requirements (namely, it has to be globally hyperbolic), and the evaporating black hole spacetime fails to satisfy this condition. Furthermore, even in a globally hyperbolic spacetime, you can't always simply state "I want a surface of constant time after the black hole evaporated". That might not exist. Hence, the problem ends up being that you picked a bad notion of "time" and tried to force your way into making it work.
A second argument is given in a 2017 paper by Robert Wald and William Unruh, two notorious scientists that believe the information loss in black holes is not a paradox at all. Shortly, they consider the ways in which Hawking's calculation could fail, and boil it down to four situations:
- no black hole is ever formed;
- evaporation is not well-described by Hawking's calculation;
- the black hole doesn't evaporate completely, but rather leaves a remnant;
- there is a huge burst of information at the end of the evaporation process.
They then look at each possibility in turn and point the following problems with each of them:
- one needs to challenge General Relativity in conditions we typically would be quite sure it works;
- the same as before, but you might also need to challenge quantum theory;
- either you can access the information from outside (in which case we would expect them to be formed at a very high rate) or you cannot (in which case it is not exactly a useful concept), with a second problem being that we would nt expect such a small object to have much information stored in it;
- a burst of information would likely require a lot of energy, which is not available since the black hole is nearly completely gone at this stage.
I must point out that, as far as I know, there are scientists pursuing each of these alternatives, so the criticism on them is also not a consensus.
Conclusions
The key point from this answer should be that this is a difficult conundrum that we don't really completely understand yet. Depending on who you are talking to, you'll hear a very compelling argument coming from a really smart person about why black hole information loss is or is not a problem. I guess this is a really good example of how science is always an ongoing project and we don't really have all the answers.
People who are disturbed by the problem often are disturbed, as far as I know, because in their understandment information loss is violating the principles of quantum mechanics, and quantum mechanics is of the greatest successes of the history of physics. This violation is due to Hawking's prediction that, if you trust his computations all the way, black hole evaporation apparently makes information vanish from the universe.
People who are in peace with information loss think so because they believe quantum mechanics is not being violated. For example, due to the technicality on the definition of "constant time" that I mentioned (the paper by Unruh and Wald provides a similar example in a flat spacetime). Furthermore, they also believe that the "solutions" are often more disturbing than the "problem" itself.
It is extremely important to notice that the issue at hand is not an object falling into the black hole, but rather the black hole evaporating after that happens. Also, it is extremely important to notice that the apparent information loss in a burning piece of paper is just a matter of convenience, but we are interested in a matter of principle.