The Gemara addresses this in 19b, and Rashi there explains the mishna; he says the issue here is that yibbum and chalitzah both clash with the obligation of a king's honor. Chalitza -- to have him summoned before the court and for someone to spit in front of him; yibbum (this is cool!) -- for him to say "I'm filling in for my dead brother" ... the king should never appear to be anyone's "understudy."
The default, then, is that the obligation of a king's honor precludes either possibility. Rabbi Yehudah is of the opinion that the king may then choose to waive that obligation, at which point nothing is standing in his way of yibbum/chalitzah. The Sages opine that the matter is out of his hands:
לא חולץ ולא חולצין וכו': איני והאמר רב אשי אפילו למאן דאמר נשיא שמחל על כבודו כבודו מחול מלך שמחל על כבודו אין כבודו מחול שנאמר (דברים יז) שום תשים עליך מלך שתהא אימתו עליך מצוה שאני:
[R. Yehudah allows the king to waive his honor and then do yibbum/chalitzah] -- Really?! But Rav Ashi said: Even according to the opinion that a chief rabbi may successfully waive his honor, a king who attempts to waive his honor may not do so, as Deut. 17 obligates us to "firmly emplace a king", i.e. you must be in awe of him! [R. Yehudah would reply that] it's different [i.e. he may choose to forgo his honor] when it's a mitzvah [situation].
Just to hash out the consequences here: if there's an additional surviving brother, let that one do yibbum/chalitzah and then the widow can get on with her life. If the king is the only surviving brother, then yes it's a sad situation that the widow can't remarry; but then again you saw in that Mishna that a king's widow is also not allowed to remarry. In short, the national interest in a leader figure overrides those concerns.
There are cases in which there's no obligation for yibbum/chalitzah (e.g. Joe's paternal half-brother married his maternal half-sister); but what's happening here is that there is an obligation, but it's overridden by external halachic factors. No different, I suppose, than the following cases:
The brother had previously sworn not to get within twenty feet of any woman in that family
There was some weird life-or-death medical issue preventing both yibbum and chalitzh [suppose either of them has a horrible contagious disease]
Or just to use the Gemara's example, if the surviving brother is a chief rabbi, according to the opinions that he can't waive his honor either.
There's a broader question that's debated -- is yibbum/chalitzah simply the mechanism to allow the widow to remarry, or is it an all-out obligation? Suppose she's 90 years old and has zero interest in remarrying. But I don't think that's your case either.