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.
Open LocalSettings.php $wgDisableCookieCheck = true; will be fix your problem.
Not really the issue you're complaining about, but i did notice you're using a private wiki and the version is 1.18.0. 1.18.0 had a bug where "Private Wiki users were always taken to Special:Badtitle on login" which was fixed in 1.18.1