I was thinking about this more yesterday, and thought back to Crossfit Endurance.
Their training philosophy could make a high fat/protein diet possible, because they do not include any long runs in their work outs really. Nothing longer than half marathons from what ive seen.
However, if you are doing a more traditional training program, long run/interval/recovery runs, then youd be better off on a carb loaded diet. So, maybe a paleo meal style like Mike suggested. My diet while training was pretty paleo without knowing it.
It really depends on your body, and itll take at least a couple weeks, if not a month for any signifigant differences to be noticable.
And to Daniel, I know of a couple elite Ironman Triathletes/cyclist that are on a raw vegan diets.