You can't do this on a PNG as the colors are stored as RGBA colors, but you can find the color index by comparing the pixel against the original palette, then swap the colors with the new palette.
Example:
$origpallete = array(...);
$newpallete = array(...);
for ($x = 0; $x < $width; $x++)
{
for ($x = 0; $x < $width; $x++)
{
$color = getcolor($x, $y);
for ($i = 0; $i < count($origpallete); $i++)
{
if ($origpallete[$i] == $color)
break;
}
if ($i < count($newpallete))
setpixel($x, $y, $newpallete[$i]);
}
}