It turns out we were having two problems with Magento ver. 22.214.171.124.
1) trigger_recollect in records in our sales_flat_quote was set to 1 for some users old shopping carts stopping them from logging in. Removing them solved this problem:
2) The cookies were being rejected for some reason. Users had to delete cookies before they could login. The following core hack worked, although it\’s a dirty solution:
Hopefully this helps someone.