Как изменять цвет текста в зависимости от результатов AJAX

Передавай в Response так же цвет, в зависимости от результата запроса. В самом обработчике php просто сделай так:

*************************
//Обработка... запроса
*************************
$data["color"] = "green"; //red, blue yellow.. other else в зависимости от результата
$data["text"] = "message";
return или echo json_encode($data); //зависит как реализовано у тебя в скрипте

И далее в JS

document.getElementById("Message").style.color = Response.color;
document.getElementById("Message").innerHTML =  '<i>' + Response.text + '</i>';

Update:

if(xmlHttp.status==200) 
{ 
    var Response=JSON.parse(xmlHttp.responseXML); 
    document.getElementById("Message").innerHTML = '<i>' + Response.text + '</i>'; 
    document.getElementById("Message").style.color = Response.color; 
}