Lo sfondo trasparente è opzione caratteristica delle immagini a 256 colori salvate in formato gif (o ico). Riprova salvando in formato gif, magari prima riduci a 256 la profondità di colore.

Non so quanto sia facile con Paint, ma con IrfanView non puoi sbagliare, perché puoi scegliere il colore trasparente soltanto mentre salvi in gif!