Is the 4-player variant unbalanced? Is there a fix?
The 4-player game is extremely unbalanced.
Greyjoys need to play fast and aggressive with building a navy to stay in the game to begin with, in a 4-player game that need is greatly expanded; if they don't get an army down south, they'll never be able to be a real competitor.
(My group is current on hiatus from playing this game as the last game we played I (as my first time as the Lannisters) took over Ironman's Bay, and stranded the Greyjoy player for the rest of the game, continually raiding his Consolidate Power so he couldn't bid on the Influence Tracks, and kept him unable to place a single starred order the entire game.)
5-player has similar Greyjoy issues, but the inclusion of Tyrell (starting in the completely undefended south) usually makes a huge advantage for the lucky 5th player.
Generally speaking, I never used to play when I don't have 3 or 6 players, however, one of my friends stumbled upon this:
Using this overlay, and the rules that come with it (no Martells, a strength 5 neutral token on Sunspear, take out Greyjoy and make Pyke unclaimable with only 4 players), we were able to have quite a few successful games.
Then... I found these:
Rumble in the South  puts everybody deep in awesome. From boardgamegeek:

4 Players: Rumble in the South
In this variant, Stark and Greyjoy are unplayable and their lands are
impassable. The impassable regions thus include: Bay of Ice, Flint's
Finger, Ironman's Bay, Seagard, The Mountains of the Moon and The
Narrow Sea. This variant is excellent at creating a true 4-way battle
with shifting alliances! However I tend to make the win condition only
6 castles instead of 7 to speed up the game.

After a full 6-player game, this is my favorite way to play. Boardgamegeek also has 3 other game variants:

4 Players: Struggle in the North
In this variant, Tyrell and Martell are both unplayable and their lands are impassable. The impassable lands start at: Highgarden, The Reach, The Boneway, Storms End and includes all lands south of there. Interestingly, this variant leaves the oceans around the southern end of the continent open, and I recommend The Arbor remain in the game as well.
5 Players: Race to King's Landing
In this variant, Baratheon is unplayable and Dragonstone is impassable. But all other areas on the board are fair game. I like this variant since everyone else, except Greyjoy really, has a shot at taking King's Landing first.
5 Players: King in the North
Despite its name, this variant has Stark as the unplayable house, with their lands and the Arryn's lands impassable. This includes: Bay of Ice, Moat Calin, The Twins, The Mountains of the Moon and The Narrow Sea. I don't like this variant as much since Greyjoy goes at Lannister, and Tyrell tends to go at Martell, leading to a relatively easy Baratheon victory unless Tyrell and Martell team up on Baratheon. But it's still better than the neutral armies in the rules!

None of the 5-player games are nearly that interesting, so what we do with 5-player games is simply add +1 to all Martell neutral tokens; it seems to be enough to slow the onslaught of destruction set on by the Tyrells. At least enough for the Lannisters to join into the fun.
Variant 4/5-player board: