City was not first a settlement. How to fix?
If you don't notice a mistake until long after (or once you can no longer roll back the moves to correct the mistake) it happens then you should just let it stand. In this case the player should get full credit for the city as if it was built correctly.

The problem with trying to penalize the new player for the mistake is it is also the fault of the other players for not paying close enough attention to catch the mistake in the first place.

On the other hand if the player was intentionally making the mistake as a way to win more easily then they should be removed from the game instead. 

You should always remember that when playing games with a new player mistakes will always happen and being a new player they have a smaller chance of winning anyways so it will even itself out in the long run.

This also applies to experienced players who make mistakes (everyone can make them) but need to be careful that someone isn't just trying to cheat. The main theory behind this is that everyone playing the game is responsible for ensuring that it is played correctly and also responsible when a mistake that is publicly knowable (like playing a city without a settlement there already) is made.