These guys basically just use the Bomberman body sprites (in Neo Bomberman, character sprites are divided into heads and bodies) with a different "Bad Bomber" head. The Bad Bomber head has no animations. So really it was just a matter of pasting the head sprite over the walking sprites that I'd already ripped earlier, and then collecting all of the palettes.
EDIT: Holy crap, one day off from the last date that I posted in this topic... 2 years ago? I can't believe it has been THAT long...