Alright, so I went a head and tweaked my entire tileset and toned down the colors a bit for them as well, while also using the new character colors you posted above. Here is the result:

I like how the tiles look now, but things seem a bit... thin now. Although, I might decide on using dynamic lights for this game so the number of viewable rocks on the floor, ceiling and walls might not be an issue.