What are the downsides to multi-classing?

There are two main downsides to multiclassing, though depending on your play style and group you may never run into the lesser of the two issues.

Falling behind single-class characters

The primary issue, and one that is more likely to impact any game that makes it past 5 levels or so, is that classes scale in power generally at the same time. Casters get level 3 spells (Fireball, et al) at 5th level, martial characters get Extra Attack at 5th level, and Rogue and Bard get Uncanny Dodge/Font of Inspiration.

If you're a wizard and you decide to multiclass into rogue before or at your fifth character level, you will forever be a level behind in your spell progression, and since Challenge Ratings take into account your character level and expect that a level 5 character will have either Extra Attacks or fireball (or other equally powerful spells), your character may have a hard time keeping up damage-wise in combat situations, because you're only a character with level 4 wizard capabilities and level 1 rogue capabilities, neither of which are very impressive compared to what you get at 5th level with either. The only thing you do gain at that point is an increase in your proficiency from +2 to +3, which isn't nearly enough to make up for the initial delay in spell/class feature progression.

Now, it is true that this impacts spellcasters significantly more than it does martial characters, but it does affect your wizard's ability to be the best wizard he can be.

A note on ability score improvements

It is also important to note here that unlike in previous editions, 5th edition D&D ability score improvements are granted by class level, not character level. This means that multiclassing into more than one class can and likely will result in suboptimal ability scores at higher character levels, but when advancing through the tiers of gameplay this effect can be more substantial.

More on ability scores

The multiclass rules (if you choose to use them) require secondary (and tertiary) classes to meet certain ability score requirements. If those requirements are ignored, it is likely that those class levels will be "wasted" as the character will display subpar performance in that class due to their inability to keep up with characters of a similar level. This is less of a problem in 5e due to bounded accuracy, but is still probably enough of a deterrent to multiclassing into more than two classes.

No capstone abilities

The second real drawback to mutliclassing, which I mentioned may not affect you based on your group and play style, is that levels are capped at 20 in 5th edition D&D, meaning that characters who multiclass won't ever get their capstone abilities (and possibly 17th/18th/19th level abilities). Once you reach level 20, you can gain no more class levels and thus you can not gain any more class features. Since most games don't reach this level of play, it's not as much of an issue, but is something to consider, especially if starting a game at high level with the intent to play at level 20.

Examples

Using your example of barbarian-druid-warlock-paladins, that's a character that's going to need at least a 13 in STR, CON, WIS and CHA. Unless your player rolled really well it is unlikely they have a character build that can even support this, especially given that the character will likely miss out on one or more ability score improvement throughout her life.

Imagine this theoretical character: barbarian 4/druid 4/warlock 4/paladin 4. This character has a proficiency bonus of +5, and has received 4 ASI's throughout his career.* However, his class features for any given class only equal that of a level 4 character. He is tier 1 in every class, and has no tier 2 abilities that can help his survivability or damage output in higher tier gameplay. He is in a party of APL 16, with 3 single-class characters and the party is facing a CR 16 monster. Which party member is going to be the least helpful in this situation at a high level of play? Probably the character who has only one attack per turn, no access to anything above a level 2 spell, and no ability to wild shape into anything but a 1/2 CR beast that can't even fly.

I can see why there is some confusion on this. The multi-classing rules are clear, but require a pretty careful reading lest you miss some of the key drawbacks to multiclassing.

As Legendary Dude said, you will miss out on late-game abilities and the like because once you hit 20th level, there's no more leveling. There are epic boons, but additional class features are effectively locked out.

This drawback applies to quite a few classes, all of whom have some pretty awesome capstones (i.e. Barbarians, Clerics, Druids, Fighters, Paladins, Rogues, Wizards). But there are intermediate abilities that remain locked out, until you reach the appropriate level. Unlike in 3.5 where taking levels in 2 different classes that provided Uncanny Dodge automatically gave you Improved Uncanny Dodge, 5e rules function more along the lines of you either have it or you don't. So you either go 7 levels of Rogue or Monk for Evasion, or you don't get Evasion.

As it relates to casters, it's important to note that the highest spell level you can know and cast is dependent upon your level in the applicable class. The spell slots available continue to increase provided you are a primary caster. For example, a Wizard 3/Cleric 2 has 3rd level spell slots available for use, but they do not have any 3rd level spells. They only get to utilize that 3rd level slot for the 1st level spells that their Cleric levels give them or the 1st and 2nd level spells that their Wizard levels give them. In this way, they've traded raw power for versatility.

Lastly, it's important to remember that ASI, and by association feats, are tied to class levels. You do not get an ASI because you reached 4th level, you get it because you reached 4th level as a Rogue or a Wizard. If you want to level dip into a little bit of everything, it will be a very long time before you see an ASI.

For instance, we have a 3rd-level Barbarian who has started multi-classing in to Druid. He's not going to be getting any more significant Barbarian abilities until 9th-level...

I would strongly disagree with you on that statement.

At 4th level, your barbarian receives an Ability Score Improvement, which is essentially a +1 to every single task that uses a single ability score. He can hit harder, he's harder to hit, he's got more HP...in 5th edition, getting that bonus is huge, because there's not a whole lot of other ways to permanently or semi-permanently augment your attack rolls/skills/saving throws/ect.

At 5th level, your barbarian receives Extra Attack. This is huge. In past editions, you could multiclass between different martial classes and still receive additional attacks. This is not the case in 5e; if you multiclassed into Fighter from Barbarian level 4, you would have to take 5 levels of Fighter to get to Extra Attack 1.

At 6th level, you get a feature from your archetype. Granted, the Totem features at this level are non-combat oriented (though all of them are pretty useful, if I remember correctly), but the 6th level feature of the Beserker archetype gives you immunity to the charmed and frightened conditions (at least while raging). Is a big bad dragon preventing your fighter from hitting it because he can't get close enough? No worries, you can just walk up to it and hit it like nothing ever happened.

At 7th level, you get two VERY powerful features. First, you have advantage on initiative rolls, which means you can take down key threats quicker or just remove a few mooks that would otherwise be giving the party trouble. Second, you can't be surprised. Ever. As long as you aren't sleeping on the job or magically frozen in place, no one can ever ambush you.

8th level presents the same benefits as 4th, so I won't cover them.

If your barbarian wants to gain access to some spellcasting, I would recommend the Magic Initiate feat (though the feat becomes less useful when you realize you can't cast the spells you've learned through it while raging) or the Ritual Caster feat. As for wildshaping, a 2-level dip into Moon Druid wouldn't be completely out of line for a barbarian. Just keep in mind that you can't use your own physical stats while wildshaped.

The 3rd level warlock you mentioned has to go through 3 levels of rogue to get that Assassinate ability. Which means that they're losing out on additional invocations and spells compared to a straight warlock. Bestow Curse is a fair bit more powerful than Hex.

The PHB says:

you'll sacrifice some focus in exchange for versatility

That statement does not refer to roleplaying. A 5th level wizard can deal 16d6 fire damage in the space of 2 rounds thanks to Fireball. A 5th level barbarian can deal 4d12+20 slashing damage in the same timeframe. A Barbarian 3/Wizard 2 can do neither of those things, and even a Barbarian 5/Wizard 5 can't do them both at the same time.