I believe that Chady is correct. To verify this, you might try

lynx -dump -source http://localhost/cookie-via-CGI.cgi
[download]

Since you said that the CGI method of setting the cookie works correctly, this lynx call would let you view the server headers (including the Set-Cookie portion) and in what order they appear when done "properly".