OK, I did another thing. The KaoUtil works perfectly.
I got @growlithecubone's custom portraits to work (I did Kirlia's myself). And yes, I know Poochyena isn't in the starter menu, I just replaced Dunsparce's grin portrait because I'm lazy. I used GIMP's indexed mode to ensure there were no more than 16 colours.
Here's what you've got to do:
First put a single pixel of a colour you're not using down anywhere on the image. This is to make sure GIMP
generates enough colours.
Next, hit Image>Mode>Indexed, put in 16 for the Maximum No. of Colors, then hit Convert.
Get rid of the pixel you drew in step 1.
After that, hit Colors>Map>Rearrange Color Map
Then drag the unused colour to the left-most side and hit OK. This colour will be replaced by pure black in game.
Go to File>Export and then Load Defaults and Export.
Right click on the image and hit Properties, then Details and it should say it has a bit depth of 4. Additionally,
it shouldn't be more than around 900 bytes or so and be 40x40 pixels big.