I see 3 ways this issue can happen -
1 built your first city, get a free palace
2 lose your city with palace, get a free palace in another city
3 load a saved game
For 1 & 2, the help says "If you lose the city containing this improvement, it will be rebuilt for free in another of your cities (if the 'savepalace' server setting is enabled)." It doesn't say whether this happens immediately or at turn change time, so I think it's OK to leave things as they are.
For 3, I had a capital when I saved the game, so I should still have it when I reload that saved game - maybe I've got dozens of units to be moved scattered all over and really want Shift-home to work. This simple patch fixes that case, should be OK for all branches.
While investigating, I found something I don't really understand. This is unpatched behavior. In the server when "load xxx" is done, savegame_load() is called and my player pointer has value pplayer = 0x7f8a1b087600, pplayer->primary_capital_id = 0, my city pcity->capital = 0. When the game is started, update_capital() is called, pplayer = 0x7f8a1b087600 is the same player pointer, pplayer->primary_capital_id is now 188, my city pcity->capital is now 1. Then I do the Shift-home, and in the client, player_primary_capital() is called with pplayer = 0x7f8865c6aa00, which is a different player pointer value, and its pplayer->primary_capital_id = 0. At turn change, update_capital() is called again, also with pplayer = 0x7f8a1b087600. Then when I do Shift-home again, in the client, player_primary_capital() is called again with that different player pointer pplayer = 0x7f8865c6aa00 but now the pplayer->primary_capital_id is correct. Do the server and client have separate lists of player pointers? that they somehow try to keep in synch?