MS Paint is very limited in its features and it has several bugs that can be troublesome, more so when dealing with formats other than bitmap.
This is a short tutorial on how to get MS Paint to do things it's not normally supposed to do.
When creating an image that needs a pattern fill, you need to decide on the colors you will use to designate the fill areas. Fully saturated colors work best because they are easy to remember, but any color you will not otherwise be using in the image works as well. You can have as many pseudo-layers as you have colors you will not be using.
Since the image for the Bahamut Star System required only two pattern fills, I used black and white.
So step one is to create the base image as seen in image one below.
Step two is to create the first pattern you want to fill with. The pattern is a separate image filled with the same size as the base image. In this case the pattern image is the background color, or two repeating lines of two nearly black greens. See image two.
Step three is to create the next pattern you want to fill with. (Repeat as many times as you have patterns.) This is the same as step two, in this particular instance the pattern is the fore color or two alternating bright green lines. See image three.
Step four is to copy the entire base image from a separate instance of MS Paint and then paste it on top of the first pattern. Before you finish the paste operation, set the background color of the MS paint instance with pattern one to the same color on the base image you want to pattern fill. Then turn off "draw opaque" in the image menu. See image four for the result. As you can see the background color now fills the background.
Step five is to do the same thing for the other areas that need to be filled. In this case the foreground of the base image. Take the previous image (the one with the background filled) and then paste it over the next pattern image, again setting the background color to the same as the color that you want to replace with the pattern. See image five.
Repeat step five for as many other colors that you wish to replace.
Note: Due to color problems MS Paint has when working in formats other than 24bit Bitmap, I would suggest working in that format and then saving the final results in PNG when done.