According to IRS Topic 431 - Canceled Debt,
Cancellation of a debt may occur if the creditor cannot collect, or gives up on collecting, the amount you are obligated to pay.
In general, if you have cancellation of debt income because your debt is canceled, forgiven, or discharged for less than the amount you must pay, the amount of the canceled debt is taxable and you must report the canceled debt on your tax return for the year the cancellation occurs.
So at first glance, it would appear that the answer is yes, those recipients are going to owe taxes.
However, there are exceptions to taxable cancellation of debt income, including:
Amounts canceled as gifts, bequests, devises, or inheritances
It clearly seems that Oliver's intention is that these amounts are considered cancelled as a gift.
Under this rule, the recipients do not have to pay taxes on the full amount.
In contrast, had the debt been considered cancelled because it was out of statute ("the creditor cannot collect" from the first quoted sentence), the full amount of the debt would have been considered taxable income and the debtors would have owed the IRS in addition to whatever harassment, costs, legal expenses, and/or payments they made on the debt to get collectors off their back. So from that perspective, John Oliver's gift was the best they could have received to help with those particular debts.