No, a new game shall not be started (that is only when the initial position was wrong). The Fide laws say:
7.4 If during a game it is found by the arbiter or one of the players that an illegal move, including not exchanging a pawn who reached the last rank for a queen rook, bishop or knight and capturing the opponent’s king, has been completed, the position immediately before the irregularity shall be reinstated. If the position immediately before the irregularity cannot be determined, the game shall continue from the last identifiable position prior to the irregularity. The clocks shall be adjusted according to Article 6.14. Article 4.3 applies to the move replacing the illegal move. The game shall then continue from this reinstated position.
After the action taken under Article 7.4(a), for the first two illegal moves by a player the arbiter shall give two minutes extra time to his opponent in each instance; for a third illegal move by the same player, the arbiter shall declare the game lost by this player. If the opponent cannot checkmate the player by any possible series of legal moves even with the most unskilled counterplay, the arbiter shall decide the result of the game.
7.4 If during a game it is found by the arbiter or one of the players that an illegal move, including not exchanging a pawn who reached the last rank for a queen rook, bishop or knight and capturing the opponent’s king, has been completed, the position immediately before the irregularity shall be reinstated. If the position immediately before the irregularity cannot be determined, the game shall continue from the last identifiable position prior to the irregularity. The clocks shall be adjusted according to Article 6.14. Article 4.3 applies to the move replacing the illegal move. The game shall then continue from this reinstated position.
After the action taken under Article 7.4(a), for the first two illegal moves by a player the arbiter shall give two minutes extra time to his opponent in each instance; for a third illegal move by the same player, the arbiter shall declare the game lost by this player. If the opponent cannot checkmate the player by any possible series of legal moves even with the most unskilled counterplay, the arbiter shall decide the result of the game.