The problem is that black holes evaporate. If the particles released via evaporation don't contain the information about the particles that entered, information is lost when the black hole is completely gone.
The proposed solution is that the information is encoded onto the surface of the black hole and thus into the hawking radiation being released from that surface.