I had a similar issue, and this was of some help.
The issue arises because the CookieCollection contained in the CookieContainer is selected based on the base Uri (Authority portion), but it is entered in some cases as the entire Uri of the original request. If you inspect the CookieContainer at run-time, you can see that the internal "m_domainTable" contains these Uri values.
To resolve the issue, I added the following lines after I get the ResponseStream (when the CookieContainer is populated):
foreach ( Cookie c in cookies.GetCookies ( request.Address ) )
cookies.Add ( new Uri ( request.Address.GetLeftPart(UriPartial.Authority)), c );
The "cookies" variable is the CookieContainer set to the "CookieContainer" property of the HttpWebRequest. There is probably some work to remove the old cookies, because I am now doubling up the original cookies sent. As of yet, this isn't an issue for my throw away application.