We have a two-way trust between Domain A and Domain B, users are able to access the sharepoints most of the time but sometimes they are getting "Access Denied" to sites or lists that they have permissions to access. Any idea why this is happening?

Which domain does the SharePoint installation belong to? Which domain users get the access denied?

SharePoint is installed in Domain A and its users in Domain B that are getting the intermitten access. The access denied they get is from SharePoint.

SharePoint needs to be configured to search users from Domain B. Try running this command and see what you get: stsadm -o getproperty propertyname peoplepicker-searchadforests [-url] <URL> Details of this command available here: http://technet.microsoft.com/en-us/library/cc263460(office.12).aspx

I get <Property Exists="No" /> when I run the command. After looking at the explination for the command it says that this is domains with a one-way trust and mine has a two-trust. I am able to see and add users from the trusted domain into sharepoint but the problem is that some users from the trusted domain get the sharepoint error message: "Access Denied".

You could use the security access checker available here: http://accesschecker.codeplex.com/ to check what permissions users that are getting the access denied have on the site collection.

Once you have confirmed that the user has the correct permissions using the codeplex tool, you might need to check the Windows event logs for security/audit related events for users that are being denied access. Also ensure that the pages that the user is attempting to see has been published and not in draft mode (if applicable). If the event log does not provide further detail then you might need to use a tool such as fiddler or netmon to debug the issue.

what exactly will i be looking for in the logs of fiddler or netmon? I checked the IIS logs and found the entry for the access denied error but it doesn't get specific on what caused it. The user has full control on the site. Here is something interesting, in order to get user in to the site an AD account was created for him on Domain A (where the sharepoint server is located) and when tries accessing the site with that account he gets in just fine but if he uses his account from Domain B (the fully trusted domain) he gets the occasional access denied from sharepoint.