You don't need to avoid colours to provide support for colour-blind people, you just need to make sure colour isn't the only thing to use.
Check out the "jelly bean" presence indicators used by Microsoft Office Communicator:
Office Communicator http://neuralyte.org/~joey/images/ux.se/UQY2K_greyscaled.jpg
(Image taken from here)
The indicator for "Available" has a double-ring; "Do Not Disturb" has a horizontal bar and the other three are basically "not available".
I'd suggest that instead of changing the background of the popup, include a prominent icon to indicate the new status - with sufficient difference in shape or detail (e.g. the double ring for "Available" shown above) that colour isn't necessary to the perception, just a nice extra.
Two last comments.
Firstly, you can do much worse than copy UX ideas from companies that spend millions of dollars on the research.
Secondly, I'm writing from the perspective of someone who has a colour vision defect (for example, the "Be Right Back" and "Away" jelly beans look the same to me, but I can tell the rest apart).