So this is an interesting issue. The problem that I was having to cause this error to come up was using the SPSite.AllWebs[Guid] collection to get the web that I wanted. Well, when the code is run under the impersonation of a user that doesn't have access to all of the webs, they run into the AccessDenied.aspx, List does not exist error. They aren't able to access the allwebs collection that the administrator can. So remember this, use the SPSite.OpenWeb(Guid) function instead! 
It will save you all kinds of trouble. Safe journeys in the world of SharePoint!
chadclarke