Thanks for the advice. I just spent some time trying to brighten the colors.
Going color by color, I tried increasing the value of the colors. I could only get the dark gray to still look good. I also saturated it a bit more. Some things (such as the water) looked better, while other things (such as the werewolves) looked worse.
Then I tried modifying all of the colors at once. Lightening them all a little bit seemed to improve things, too much of course and contrast started to suffer and hues were shifting. Here they are lighter:

Also, just to be clear, these are not going to be shown at this size. I am working on them at 800% which seems about right.
I think that I need the outline to provide contrast. I could increase the tile size to get more detail, but then I wouldn't be able to make things as fast. I have too many half-made games lying around. I want to finish this one.