судя по всему, действительно на стороне сервера $HTTP_REFERER либо пуста, либо неверна...
а браузер тут не при чем
чтоб убедиться, попробуй отправить не header(Location: $HTTP_REFERER), а что-то типа header(Location:
http://imho.ws) - если редирект пройдет - браузер отпадает