¿En windows o en GNU/Linux? Porque me suena a que dependerá de la capacidad de la consola y no de la de python el hecho de cambiar el color.
Windows ->
http://code.activestate.com/recipes/496901/
BASH (GNU/Linux): un ejemplo por acá:
http://linux.derkeiler.com/Mailing-L.../msg00893.html
(por acá la lista de colores:
http://www.tldp.org/HOWTO/Bash-Prompt-HOWTO/x329.html)
Saludos.