I just installed Linux Mint 18.3 and to my surprise colors in Vim changed!
Vim in the terminal on the left has the color scheme I've always seen and got used to. Vim in the terminal on the right has the new colors. On the left, I'm ssh'ed into a different machine. On the right is my new Mint.
Both windows are of the same terminal emulator, with the same profile settings, so the issue is not with my color scheme.
How can I get the normal colors back?
Update: It looks like the old colors flash for a tenth of a second when I open a file, but then the colors are reverted to new. As I wrote in the comments, in both cases, :colorscheme returns default.

:colorschemeschow?:verbose highlight normalto find the script that last set the "normal" highlight group. Runecho synIDattr(synID(line("."),col("."),1),"name")to find a highlight group in effect at the cursor position. Combining them you can find out which script set the colors at the cursor position:exe "verb hi " . synIDattr(synID(line("."),col("."),1),"name").:colorschemesaysdefaultfor both.:verbose highlight normalsaysE411: highlight group not found: normal,:echo synIDattr(synID(line("."),col("."),1),"name")doesn't print anything.