They don't stack because they are both effective size increases, per this FAQ.
I don't think they are both size increases. The feat is, but the evolution just increases the die. The difference doesn't come up until d8, the next size up would be 2d6 but the next die up would be d10.
That puts you on the other size chart then, but I could see it getting confusing and being disallowed on that alone.
Well, they don't read like they are, but if you look at the faq (specifically the part that I made bold) :
As per the rules on size changes, size changes do not stack, so if you have multiple size changing effects (for instance an effect that increases your size by one step and another that increases your size by two steps), only the largest applies. The same is true of effective size increases (which includes “deal damage as if they were one size category larger than they actually are,” “your damage die type increases by one step,” and similar language). They don’t stack with each other, just take the biggest one. However, you can have one of each and they do work together (for example, enlarge person increasing your actual size to Large and a bashing shield increasing your shield’s effective size by two steps, for a total of 2d6 damage).
Now personally, I think the text in the faq is a little unclear, or at least a little nonsensical. The faq talks about effective size increases and then lists “your damage die type increases by one step”, which in no way relates to an effective size increase. Both improved natural attack and the eidolon ability you mention simply state that the attack is particularly deadly or leaves vicious wounds (neither of which equate to something being effectively bigger), but that's just my opinion.
Eidolon's are very very powerful, but having or not having a damage die step probably wont be what does or does not break your game.
I'm not certain I agree with the FAQ though. At least the part about actual size increases not stacking with effective increases. That means an eidelon with that evolution doesn't get much benefit from enlarge person or possibly even the Large size evolution.
That is not what it says. Read the last sentence quoted by Amrel -- you can get one actual size increase and one effective size increase.
And the Large/Huge evolution modifies the eidolon's base size -- it is not a size increase effect at all.