El problema no es con el redireccionamiento en sí (header .. location) sino de "donde redirecciona" ..
La página que redirecciona se obtiene del HTTP_REFERER (página referida) y si no se puede obtener, ... sucede eso que mencionas.
Lee este mensaje que se trató el tema:
http://www.forosdelweb.com/showthrea...hreadid=159800
Un saludo,