Unlike SP.UI.Status you have no direct way of setting the color with notifications, but since it is a simple HTML string you are adding you decide what goes into the notification area.
I havent tested it, but the following syntax should be perferctly legal:
SP.UI.Notify.addNotification('<span style=\'background-color:red\'>Operation Complete</span>', true);
Edit:
I debugged the notify class and saw it build up spans depending on weather tooltip and onclickHandler was set (check out the _addNotificationInternal method in CORE.debug.js).
The classes used are s4-noti, s4-noti-noti, s4-noti-in1 to -in3 all defined in COREV4.css (_LAYOUTS\\STYLES\Themable\CoreV4.css). Here you will also see that lots of the colors are actually controled by the theme chosen.
I played around with editing them runtime using the css rules:
function notifyMe()
{
var sheet = document.styleSheets[6];
var rules = sheet.cssRules ? sheet.cssRyles : sheet.rules; //cross browser rules
for (i=0;i<rules.length;i++)
{
if (rules[i].selectorText.toLowerCase()==".s4-noti")
rules[i].style.backgroundColor = 'red';
if (rules[i].selectorText.toLowerCase()==".s4-noti-noti")
rules[i].style.backgroundColor = 'green';
if (rules[i].selectorText.toLowerCase()==".s4-noti-in1")
rules[i].style.backgroundColor = 'blue';
if (rules[i].selectorText.toLowerCase()==".s4-noti-in2")
rules[i].style.backgroundColor = 'purple';
if (rules[i].selectorText.toLowerCase()==".s4-noti-in3")
rules[i].style.backgroundColor = 'magenta';
}
var nid = SP.UI.Notify.addNotification("test", true);
}
This didnt completely style them, but should give you an idea on how to edit them as needed.