If you were using Paint, the image isn't paletted at all, not to even mention if the palette is correct. I imagine the tool would choke on this.
Besides, even if Falko's tool managed to cut it, the spritesheet would be useless.
Start with using a real graphics editor.
There are many options, the forum is full of references.