have you read about chlorophyl? some said it can give your soap DOS, and the color didn't stay green after a while. i was just reading about this exact topic last night, as i was also in the looking for a green natural colorant. dang, i cant remember who the exact poster was who started the thread about this. do a search, i think you'll find it.
what about chlorealla like ravenscourt apothecary does to her soaps? it's a beautiful shade of green, no DOS according to her (i specifically asked), and the shade, altough it does fade a lil bit with time, but it doesnt discolor the soap totally.