Así es .. las cookies y sessiones no quedarán disponibles para accederlas (por $_COOKIE .. o $HTTP_COOKIE_VARS .. ) hasta la pròxima petición al servidor: Una recarga de página en tu caso ..
Para eso .. puedes probocar esa recarga de página automáticamente al no existir tu cookie y crearla ..
Código PHP:
if ($HTTP_COOKIE_VARS['lng'] == FALSE)
{
setcookie("lng", $lng , time()+60*60*24*100, "/");
header("Location: ".$HTTP_SERVER_VARS['PHP_SELF']);
exit;
} // etc ...
Así recargas la página cuando creeas la cookie .. la cookie existe y pasa a tus elseif que tienes deacuerdo al lenguaje seleccionado .. que lo recoges de tu variable que viene por GET en el URL ..
Un saludo,