mspaint should be easy to get going in wine I would have thought. Although really as far as windows apps that are simple - mspaint is awful. It's got awful image quality & supports 0.01% of filetypes.
It has almost no options for saving filetypes and if you rely on mspaint to save images destined for the web, well its your bandwidth..
I would suggest looking through the ubuntu repositories for some command-line image converstion tools. Should be easy enough to create a icon on the desktop which you can drag/drop & convert files.
I would be happy to help if you would like to do that.
Edit: Check the Netpbm package.