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,