The mere fact that an employee has been let go would be hard to count as personal data. The details around it can be another matter entirely.
People come and leave employment all the time, sometimes of their own accord, sometimes of the company's. It's usually pretty easy from a third party perspective to distinguish when which occurred though.
The details surrounding the departure are what could be really damaging, however. If the employee was fired for cause and word got around, it can damage their reputation and ability to find employment more than having to address this in an interview as the employee cannot respond to the word-of-mouth account to balance the picture.
I would talk to your legal department and, assuming they give you the okay, write to the ex-employee stating that unfortunately, word about their dismissal has gotten out but not the details surrounding it*. Profusely apologise and assure them that you will do everything in your power to ensure no more details are leaked.
Then go deal with your leaker. How far you will want to go with this very much depends on what information got out. You can get away with a verbal warning if the mere fact that the ex-employee is now an ex-employee was all that got out, but other details may warrant stronger disciplinary action.
*Figure out if this is actually the case first. If it is not, I highly recommend you go back to your legal department and listen to ONLY what they have to say.