Most of the answers so far say that king-making can be an acceptable feature of a game. However, there are certainly people who don't like it, whether they are the king-maker or not. As such, making a game that avoids king-maker situations is a good goal, not because it's bad, but because it's seen as bad by some (many?) people. King-making is especially annoying in more competitive games, or with competitive players. Such situations can't be solved outside of the game, with house rules on sportsmanship, bribes of pizza, or playing badly to give others a chance. There seem to be far more games that don't try to solve the issue, so making games that try to avoid it in mechanics may prove to be a defining feature of your game.

If a player wants to not win and instead be a king-maker, there's not much you can do without making a low-interaction game, or making it so that players' actions have little meaning. So it's better to concentrate on avoiding accidental king-making, instead of deliberate.

It's a difficult problem to solve. It comes down to the existence of "lame-duck" situations, where a player is unable to win, but is still playing. For example: when there aren't enough VP cards in the bank in Dominion to be able to come back, or if the other players have boxed you in in Settlers. This is not a terribly fun position to be in for some people, including me.

One way is to make players unaware as to who is further ahead, so that someone who is unable to win is unaware that they are. People can usually have a fair idea of what's going on, so this works better when there's lots of hidden information. This may be undesirable if you'd like to keep other kinds of player politics in your game, though.

Another is player-elimination. This is not great for casual games, because this makes players sit and do nothing, or go elsewhere and forget to care about the end of the game, which leaves a bad impression of a lack of closure to the game. And it is good to make a game cater to both hardcore-competitive and casual-fun players. You can't get the hardcore players without them playing casually, at first.

You can make a system where even the player coming last can still win. You can make it so that, as long as the player coming last keeps making intelligent moves, then they can cross some kind of winning condition without the other players advancing much at all. This requires a game with a lot of interaction, so the losing player can obstruct all of the opponents while still advancing themselves. The danger is making it feel like the rest of the game didn't matter.

Make the players team up into two teams. Turn the 4-player problem into a fake 2-player solution. This is something your game would have to be thoroughly built around, and thus is not a solution that can be used in most games (unless you want to specialise and only make team games).

I rather like the method used in Puzzle Strike 3rd Edition. There's no win condition. Players just see who is in the best position when the end-game situation rolls around. The timing of the end-game situation is somewhat difficult to predict, but (at least in this case) can be influenced by players. "Who's in the best position" can't be so static as to feel like little can be done about it, but also can't be so dynamic as to feel random. Sirlin details his design decisions on this here: http://www.sirlin.net/blog/2012/4/30/puzzle-strike-casual-play-matters.html (The two free-for-all sections are on this topic.)

So, to answer your question, "can it be fixed?": Maybe. It doesn't appear to have ever been totally solved, only reduced, and most solutions have some kind of drawback or can only be used for certain kinds of games. The solution you use for your game is likely to be dictated more by the game itself than by suggestions found on forums. Just keep testing with both casual and hardcore players.