First of all, are you decompiling and recompiling the sprites correctly? You need a sprite compiling software, such as sprite explorer. You need to make sure they're 8bit bmp's before compiling (in photoshop go image > mode > indexed color and then save as 8 bit bmp) all sprites in an animation must share the same palette too, so if you do that process on the first, the next frame in the animation use previous instead of exact or whatever it comes up with when changing the image mode, so you keep the same palette throughout the animation. You must also make sure the dimensions of the sprite are a multiple of 128 (128x128, or 256x256, or 128x256, 512x512 etc) for it to work in half life, 512 is the maximum size you can use in half life for sprites, beware though, a long animation animated at 512 with a 256 colour palette may cause fps drops ingame.
Good luck.