Well I'm assuming it must be photoshop then, cause i'm really puzzled as to what the problem is. I use Ulead Photoimpact myself, and I was able to extract a skin, convert to tga, do a bit of editing in photoimpact, convert back to blp and get it to show up in the map, all in under 5 minutes.
Try my skin, see if it works for you. Its the paladin hero, if it works in game, you should see two letter 'H' 's on his front torso, and two letter 'I' 's on his back. (I tried to say 'HI', but that didn't work cause I didn't realise half the torso skin was his front and the other half was his back).