After thinking on this some more, it might be the case that the Change Shape ability doesn't specify a specific ooze because the Pudding King can, in fact, transform into any ooze.
The Pudding King magically transforms into an ooze ...
It just says "an ooze", meaning any creature with the "ooze" type.
Given that (if we ignore the Oblex from Mordenkainen's Tome of Foes, which wasn't yet out when Out of the Abyss was released) the Black Pudding was the most powerful ooze at the time, which matches his own CR, it is likely that the Black Pudding would have been the optimal choice, but technically he can transform into any ooze he chooses.
This does raise the question of whether he could technically transform into an Oblex or not*, and whether an Elder Oblex (CR 10) would be too powerful for the party (which would usually be about level 6 or so by this point), but on the other hand, since the specific ooze he transforms into is up to the DM, it would be their call to choose the most appropriate ooze from a balance, as well as from a narrative, perspective (for example, if the party still has half a dozen NPC allies picked up along the way, like Fargus the Halfling, Hemeth the Duergar, and most of the NPCs from the drow cell you start off in, then a CR 10 creature might be the only way to actually challenge the party at that point).
*Just to address whether the Pudding King can turn into an Oblex, or any other ooze with a higher CR rating than itself, I will point out that nowhere in the text of the Change Shape action is a limit mentioned on the CR of the creature it can turn into. Contrast this with the Change Shape action of, say, the Ancient Bronze Dragon (MM, pg. 107):
Change Shape. The dragon magically polymorphs into a humanoid or beast that has a challenge rating no higher than its own, or back into its true form.
Because it is called out in the text, the Ancient Bronze Dragon has to obey that restriction, but in the Pudding King's stats, no such restriction is called out, so there is none. Of course, as I said earlier, there was no ooze greater than CR 4 at the time when Out of the Abyss came out, but as it stands, RAW, he can turn into an ooze of any CR.