No tengo ningun tema a mano que modifique la barra de navegacion, pero para que se ponga en otro color tienes que modificar el archivo Theme.xml que hay dentro de la carpeta com.android.systemui, en la linea que contenga el nombre nav_bar, ya te digo que no tengo ninguna delante para decirte el nombre completo pero debe hacer referencia a la barra de navegacion.
