Use Photoshop or another good graphic program, if the texture's color indexed (_ci) then save the pallete, if not then don't worry about it.
Scale the image up to 400%, I use nearest neighbor scaling to keep the pixel look (1 pixel now = 4 pixels in a square) do something to keep the same look of the old texture, use the blur tool if you want, add some noise maybe, paint it from scratch, whatever you want just make a new texture at 400x the old one.
I've found _ci images don't work if saved in photoshop, so I make the new texture in RGB mode, then when done, I load the original pallette (switch to color indexed mode), dether the image, and copy paste it into MSpaint, save out with that.
- MiLO83