It's a silly rule, but as written, they get Literacy as soon as they multiclass to anything else.
***HOUSE RULE ALERT***
Literacy is a cultural thing, not a class-related thing. I mean, why is it that every warrior who uses a chaotic, brute-force fighting style is assumed to be an ignorant savage? The Barbarian class has some very appealing features even to the cultured city-dwellers, after all, so it's not really fair to assume everyone who started as that class doesn't know how to read.
So, what we did IMC was make Literacy into a racial/cultural thing. The PHB races all start literate unless they come from a primitive society (in which case the DM will usually give them something else to compensate, anyway, like 2 ranks of Wilderness Lore). Monster races are usually assumed to be illiterate unless specified otherwise.