Here we go!

<apex:page controller="status" sidebar="false">
<apex:form>

<apex:pagemessages />

<apex:commandButton value="Search" action="{!getRecords}" rerender="table"/>
<apex:pageBlock >
<apex:pageBlockButtons location="top">
<apex:actionStatus id="sorting">
<apex:facet name="start">
<apex:outputText value="Show me!!!!!!!"/>
</apex:facet>
</apex:actionStatus>
</apex:pageBlockButtons>

<apex:outputPanel id="table">
<apex:pageBlockTable value="{!opps}" var="o">
<apex:column >
<apex:facet name="header">
<apex:commandLink value="Opportunity Name" rerender="table" action="{!doSomething}" status="sorting"/>
</apex:facet>
<apex:outputField value="{!o.Name}" />
</apex:column>
</apex:pageBlockTable>
</apex:outputPanel>
</apex:pageBlock>
</apex:form>
</apex:page>

public with sharing class status{

public List<Opportunity> opps {get; set;}

public void getRecords(){
opps = [select Id, Name from Opportunity limit 10];
}

public void doSomething(){
system.debug('hi');
}
}

Always start with a clean browser refresh.

Issue 1:

Set page to API 15

Click search, then the header opportunity name, no actionStatus

Change page to API 16 and repeat, actionStatus shows

Issue 2:

Set page to API 15 

Click the header, actionStatus works!

Click the header again, tricks! It does not work.

Change to API 16 and repeat, actionStatus works every click

Hint: Remove  <apex: pagemessages/> component and you will have no issues with API 15.

That was fun,

-Jason