HTTP user agents enforce a domain "firewall" to prevent one site from setting, accessing or modifying cookies from another domain. A subdomain can set cookies for it's own root domain though. So site1.example.com can set cookies for example.com which will be sent by clients to site2.example.com. But as you found, no subdomain on example.com can't set cookies for example2.com or any other domain.
See this wikipedia article for details:
http://en.wikipedia.org/wiki/Same_origin_policy
Can you use subdomains for this? If not, I think you'll need to re-architect the solution. I suppose you could insert something in the URI in the redirect which contains similar info.
Aaron