FWIW, I wasn't complaining your use of Paint.NET. I was saying that I couldn't find a way to preserve the specific palette information when saving a file using Paint.NET. But I'm not as experienced with it, so I wanted to see what you were exactly doing to generate the image using one of the newgrf palettes.
Anyway. I saved your image, and did the following to apply the newgrf DOS palette, using GIMP Portable on Windows (the only program I have available right now):
=> Save one of the palette files from the
page transportsman linked
=> Import the palette to GIMP
==> Open the Palettes dockable window by going Windows / Palettes
==> Find the Palette menu (see attached image), and go to Palettes Menu / Import Palette
==> When the Import Palette dialog opens, pick Palette File, and click Import button
=> Open the image in work, TiB53M6.png
=> Switch the color space from paletted to RGB.
==> Image / Mode / RGB
=> Apply the NewGRF palette that I imported earlier
==> Image / Mode / Indexed
===> Chose "Use custom palette
===> Chose the palette we just imported
===> Uncheck "Removed unused colors from color map"
===> Click Convert
When GIMP applies the palette to the image, it may use one of the animation colors. You will probably need to use other tools to verify and adjust the image as needed after the conversion.