Wenn man in PHP einen Cookie setzen will und dann direkt die Seite erneut aufrufen will (z.B. weil die Cookiedaten erst dann in PHP verfügbar sind), muss man das in der umgekhrt logischen Richtung machen, weil der Cookie sonst nicht gesetzt wird.
Also zuerst neue Location setzen, dann den Cookie.
header("Status: 301");
header("Location: " . $url);
setcookie('name', 'value', time()+(3600*24*350), '/');