A compromise between the gray background and the new background would be good I think as our prince kind of blends in too much now. Just a BIT more contrast.. because the background is almost as dark as his hair now. It is better though for sure, just perhaps a little TOO dark now (only by a tiny bit, I'm a perfectionist).
Also I disagree with people about the underwater colour needing to be more drastic... (I noticed it before) You don't really want people to go "OOH he changed colour" when it happens. A subtle effect is much better; like in most 3D games the colours change when you go underwater and it's not an "OH" moment... you don't even notice it! Though I do think you have it okay now, I'm just saying, I disagree with the others here 
And yeah, definitely like the palette changes throughout. Great work as per usual!
Hmm... I think you are right, it needed some contrast - specially after inserting the darker palettes for sprites in caves. I tweaked the background a bit:

Regarding the VWF, I'm not sure about how to proceed anymore. I thought about implementing Link's Awakening VWF edition font at first, but I think that a bigger font would fit this game better. So I made this one:

And I think it looks fine to be honest, however I can't help but think that the gap between the lines is HUGE. I'm considering doing some crazy stuff to implement a 16px height VWF with two different fonts that looks like this:

But before doing that I wanted to ask you because I don't even know anymore - do you think that this would actually improve the game? I don't know because I'm really crazy about font stuff, but this is a text-based game after all.