Wow my art popped up
I tried two different ways to convert Eyecraft's meteor to C64 colors, while attempting to maintain his level of detail, both are just palette swaps, not selectively re-colored:
Eyecraft, if yer reading this, I apologize, haha!
That's my best shot
EDIT: Tried again (right image)
Hopefully, the above pic helps those that haven't attempted using the C64 palette for dynamic richly detailed sprites, like this meteor, to understand my challenge. Eyecraft used 12 colors. The C64 palette only has 16. It's impossible to make something like this look good.
Yeah I had to eat some colours with my effort there. But it's not a huge issue. It doesn't matter so much how many colours there are, just what value ranges the colours that you have can cover. Space is a slightly difficult subject for c64 since you don't really have the near-blacks to work with. You basically have to make your game deal more with lighter areas than a tonne of shadow. That's what I think, anyway.
In regards to your mockup, McClaneGames is right, you need to make your character pop out more. Try using warm colours for the character to contrast with the cool colours of the asteroids. Your asteroids are also very square and flat. Try giving more volume to them if you want to add more depth to the graphics. Also if you're going to have a grid-based level like that, why not make larger asteroids that occupy 2x2 grids? Just to help break it up a bit. Or even start working with tiles. This is assuming the asteroids stay fixed in place, anyway.