Chlorophyll is a definite vegan, all natural solution! You can buy the stuff in liquid form at decent health food stores. I haven't tried it myself yet (although I've been meaning to), but I saw it used on a cooking show last year where they put a little bit in some pasta dough and it turned it a nice, deep green like you're looking for.
Ahh fantastic, thank you! I will check the health store before I resort to E numbers, vegan though they may be :)
Chlorophyll makes a very nice sense really, considering it's for trees! :D