Lightning Component aura:iteration is throwing error upon rerendering

It's possible it's the same bug. Try wrapping your component with a span, see if it goes away.

<aura:iteration items="{!v.contacts}" var="p">
  <span>
    <c:ContactItem fullName="{!p.Name}" accountName="{!p.Account.Name}" />        
  </span>
</aura:iteration>

Obviously if this fixes it, it's not your issue it is the frameworks issue and should be solved here soon.

After spring 17 release <SPAN> solution will not work.

You will receive the following error in Spring 17 Release:

This page has an error. You might just need to refresh it. render threw an error in 'markup://aura:html' [The HTML tag 'SPAN' is not allowed.] Failing descriptor: {markup://aura:html}

Workaround : Use <Div> tag instead of <SPAN> tag as in the following example:

<aura:renderIf isTrue="{!v.testingArray.length > 0}">
    <DIV>
    <aura:iteration items="{!v.testingArray}" var="opp">
        {!opp.name} <br/>
    </aura:iteration>
    </DIV>
    <aura:set attribute="else">
        Array empty
    </aura:set>
</aura:renderIf>