thats the thing.Photoshop or GIMP needs to be used essentially. Both allow you very custom editing and allow you to restrict the number of colors and compress it effectively. I personally use GIMP because I don't pirate, its almost as good, and its free.
EDIT: And Octix, its likely the code you have. Try using a different texture. What texture are you using? I recommend trying out purple Marth or something.
I have like 20+ textures on
CFx3
Kirbyx2
Lucariox3
Marthx2
Ganondorfx3
Luigix2
Mariox2
Lucasx4
MKx4
Pikachux4
I thought there was no limit on textures?