Converting an image in Max or any image editor is generally straightforward. For Max, open the material editor, right-click the bitmap node and choose Render Map... this can now be rendered to any file format that Max can write to. Now load that new bitmap into Max and replace the current bitmap in your material with the new bitmap. There are also many automated tools for that. Probably a script on Scriptspot. You can also use other programs (like Irfanview, XNViewMP, Corel PHOTO-PAINT, etc) to batch convert. You'll just need to use Google to learn the process.
