Runtime Color-Changing in RTS (based on player's color)

[Vuen]

Ok. Here's what I need. You know how starcraft have all the sprites of the units with a color magenta as the team color, and when it blits it replaces all shades of magenta with the color of the player that owns that unit? I need to replicate that effect. I have an old sub that could do it for me:

    For i2 = 0 To 49
        For i3 = 0 To 49
            pixel = GetPixel(Picture1.hdc, i2, i3)
            If pixel <> 0 Then
                For i4 = 0 To 15
                    If pixel = RGB(90 + i4 * 11, 0, 90 + i4 * 11)
>> Then SetPixelV Picture1.hdc, i2, i3,
>> RGB(Color(1, 1) * (i4 / 16), Color(1, 2) * (i4 / 16),
>> Color(1, 3) * (i4 / 16))
                Next i4
            End If
        Next i3
    Next i2

(the variable Color(1, #) refers to the three values of RGB the magenta will be replaced with)

and I could easily convert it to my directdraw code. I would have to make the game blit the original sprite to a spare buffer, replace the color, and then blit what's on the spare buffer to the backbuffer and then clear the spare buffer. The problem is that I'm afraid it may be slow. It was terribly slow the way it is now, but even if I convert it to directdraw I don't want it to end up being slow later. Isn't there a way I can palette the sprite's surface so that I can just change the palette indexes' colors, blit directly to the backbuffer, and then change the palette back?