Then I tried to sketch first and it worked great. Here's the process:
1. draw by hand on paper
2. scan it (I take photos with my phone)
3. scale it down to the size you need
4. draw the outline (make sure two pixels do not touch except diagonally)
5. color with base colors
6. add shading
For steps 5 and 6 make sure you pick a consistent palette beforehand. Something with limited set of colors (say, up to 24) works best.
P.S. You can check the graphics I created this way in my Twitter feed (@mbabuskov). Look for the horse-shaped robot and the spaceship images and see how those look way better than other stuff I drew earlier.
My best suggestion would be to actually go through some exercises in the books I mentioned. You should see massive improvement within days.
To make good pixel art, or any other kind of art really, first you must learn to see shapes in a particular way that's not intuitive for non-artists. It's a bit hard to explain in words, but if your mind hasn't learned that trick, your shapes will always come out wrong and you won't know why. Sketching allows you to learn that skill quickly and easily, while pixeling has so many distractions that IMO it's almost impossible to learn from pixeling alone.
With the right approach, as described in the books I mentioned, most people see obvious and major progress after just a day or two. I'm not exaggerating at all, it took me literally one day of sketching with Betty Edwards' book to go from "I can't draw, it must be genetic" to "I can draw anything right if I look hard enough".