E' il comportamento corretto.

Aggiungi un parametro all'URL dell'header location tipo error=1 e poi in quello script vai a visualizzare il messaggio se è presente il parametro in $_GET.

In ogni caso, utilizza URL assoluti per l'header location.