MediaWiki 1.18.0 PHP 5.3.5-1ubuntu7.2 (apache2handler) MySQL 5.1.54-1ubuntu4
If you check the browser at this time, you can see that the cookie is now present. Pressing the login button subsequent times results in logging in as expected, and success continues until the cookie is removed or expired at which point the error will occur exactly once.
I have made sure that the browsers are accepting cookies, in fact, they have the cookie in question. I have also verified that my systems session save path is valid and writable. I have also attempted to disable cookie checking with the setting $wgDisableCookieCheck but this did not change the behavior at all. Any suggestions would be much appreciated.