Clear your History and Website Data (under History menu).
You'll have to do it quickly when Safari boots up and maybe multiple times until all the history is cleared but it will fix your problem.
It seems that local (non iCloud) History data from Mavericks was conflicting with the iCloud synced history.