While many of these issues were resolved by setting up a secure store id to pull data on the users behalf, I struggled with one particular problem. A site admin had a data view web part that was using REST and pulling data in from another SharePoint sites list using windows integrated auth. Usually this means that you haven't setup Kerberos Constrained Delegation correctly but I knew this wasn't the case.
After hours of research I stumbled across this older post which talked about a hotfix that set the asp.net impersonation to allow anonymous. Specifically:
“This hotfix updates the .NET 2.0 framework's System.Web assembly and makes a major change when aspnet:AllowAnonymousImpersonation is set to true in web.config. Instead of code running under the application pool account as is traditional, code now runs under NT Authority\\IUSR – anonymous. If you have any code that depends on an authenticated identity or the specific app pool identity – SQL connections that use integrated security, for example, the code will break with Access Denied errors.”
I decided to test this theory by setting the aspnet:AllowAnonymousImpersonation to false and the web service calls started working!
<appSettings><add key="aspnet:AllowAnonymousImpersonation" value="false" /></appSettings>
I hope this helps others out in the community that are seeing these types of auth issues.