Agreed about trees. Maybe. At any rate I'm cautious of using black in the background since I like it low contrast/fogged. I notice now that I did have a darker but not black color available. It's used on the underworld tiles.
Now it looks a bit wimpy. A hue shift difference might improve the situation.
The fish lost a bit too many of its lines I think, so I added a few.
I also wanted to lose some on the top of the Goomba head. Not sure how that works. Looks like I was too aggressive. It's easier to subtly lose line on the curved bits.

Well, the animation sort of works, but it looks kind of strange.

Should Mario have a mullet? He's a bit blocky there. His legs/feet are kind of rectangular, and the lack of lines around the hand bothers me but as soon as I tried to add some he looked 'cut-out'.