Perhaps I've missed the boat here, but I was under the impression that you did NOT have to have cookies enabled to log in to a Drupal site.
Someone had trouble with a log in on my site yesterday. Turns out their cookies were set to not accept cookies. They tried to log in, the Who's online module showed them as online but they could progress no further.
I have 4.6.3 and have not modified anything related to this part of Drupal.
Should this have happened? Would it have anything to do with my hosting company upgrading to PHP 4.4.0 ??