La cuestion es si os pasa solo con algunas imagenes o con todas. En el primer caso hay algo mal (a saber que...), pero en el segundo quiza la solucion sea facil:
Si os habeis fijado alguna vez, en una instalacion limpia de Windows 2000 (no se si en XP pasa lo mismo) el paint solo es capaz de guardar ficheros como BMP, aunque lea otros formatos. Esto se soluciona instalando cualquier visor de imagenes (ACDSee, PicaView, etc), de forma que se quedan en el sistema los plugins necesarios para manejar otros tipos de ficheros. Quiza se os solucione vuestro problema (re)instalando alguno de esos programas...