La regola dice che gli header non possono mai trovarsi dopo l'output al browser, mentre tu ce li hai proprio lì.
Nel vecchio server probabilmente funzionava lo stesso perché faceva output buffering.
Quindi, senza bisogno di soluzioni drastiche, hai due possibilità: o sposti l'invio degli header nello script, oppure modifichi l'impostazione dell'output buffering su php.ini, sempre che il gestore di hosting te lo consenta (non ricordo qual è l'impostazione esatta)