Well, it's pretty simple once you know how do to it. What I did was I painted new provinces in Ultimate Paint found in the downloads on this site, then saving it as .gif with palette. Saving it as .lbm would mess up the palette completely, which is bad.
Then, using Imageconverter also found in downloads, I just converted it back from gif to lbm. That's pretty much it.

Then, of course, comes the editing of the startpos file, adding settings of all new regions and such, which is much more time consuming than the painting part.