
http://i2.photobucket.com/albums/y13/tocky/cpc-animalmen-colortest.png
Nice frog and rhino

These are a bit more stylish than practically any actual CPC graphics, so you've had a win there.
The palette makes sense for what you seem to be aiming for (sort of toony)
.. however it lacks contrast. One common way of getting things to look better on CPC was to exaggerate the lighting and the lines (over-rendering, in short, which would disguise the shortage of shades that the rendering was actually done with)
I feel like i'm just blocking colours on top of one another. I try to play attention to the light and how it hits and what it hits but mostly what i end up doing is blocking on colors and adding more lights or shadows, or mixing at the edges where it looks wrong - which works okay, but it kinda keeps me from making anything that looks properly hairy or leathery or whatever - i rely on the colours a whole lot. Can I maybe get some pointers on how to handle this stuff?
Exaggerate like mad. Seriously. Mostly, Mode 0 CPC games did not achieve a good level of texturing, but those that did, exaggerated their lighting vastly, for instance.
One of the best games to look at for the kind of art you are doing here is Xyphoes Fantasy.
http://cpcwiki.eu/index.php/Xyphoes_FantasyIt has graphics that are considered to push the CPC to it's limits.
Have a look at the screenshots at the link and/or emulate it using Arnold or WinAPE; it had large (huge by CPC standards) animated animal sprites. I think you will find that texturing is used sparely per se; most texturing is more color interleaving than brightness interleaving.
It's also worth considering, on my 1280x1024 screen, 300% - 400% zoom matches 'native' CPC Mode 0 pixel size. Knowing this may effect your texturing choices.
The details of CPC stuff are here:
http://www.wayofthepixel.net/pixelation/index.php?topic=3225.msg40939#msg40939 and here:
http://www.wayofthepixel.net/pixelation/index.php?topic=7639.msg90277#msg90277 (which also includes CPC+ info, which might be interesting to you)
To sum up, you have three issues here:
* Your palette does not exploit the quirks of the image limitations as well as it could ( for example, that pink is only used on the kiwi -- I would swap it for orange, or swap all the orange for pink, and use the extra palette slot on a dark blue, which tends to be quite versatile; and the lightest blue might better be a bright cyan instead (#0FF))
* Your characters have good CPCish outlines, the inside structure is not really worked out as well as it could for good-looking CPC rendering.
* your lighting choices are directly obstructing your ability to render texture clearly. Exaggerating it more will allow you to exaggerate the textural difference between surfaces.
Somewhat crappy edit:

I don't endorse all of the changes I made, but they should give you some idea what I mean.