First of all, check that they have a clean IE cache, have restarted their browser etc.
Check that they don't have an incorrect stored user name and password against the site host name on their Windows profile.
Ensure that the permissions on the site in question haven't been amended without your knowledge.
Ensure that they are in the correct AD group (if necessary)
Have a look at the IIS logs and ensure that their credentials are being passed in. (Search for their username). If they are not, you'll need to ensure that the SharePoint site is in the correct zone on their browser to get credentials passed in. (Trusted sites?)
Have a look in the Windows Event Logs and ULS logs when they try to hit the site to see if anything unexpected is happening
Ensure that you don't have any Web Application policies set up (go to Central Admin -> Application Management --> Policy for web application) which would deny these specific users access.
Ensure that the user account directory path, and people picker settings for the site are not stopping them from getting access:
stsadm -o getsiteuseraccountdirectorypath -url <site url>
stsadm -o getproperty -pn peoplepicker-seachadcustomfilter -url <site url>