Most of the time users cannot login now after upgrading to 1.0.8... are sessions working correctly in 1.0.8?
Once in a blue moon all of a sudden they are able to login.
The version of Apache or PHP doesn't seem to matter either.
Have you checked its not mod_security causing problems?
Have you checked they've cleared their cookies and cache?
Sessions should work unless something required is missing