Several points, just to try to cover all the possibilities...
1) Have the passwords to any of the accounts ever been changed? If
so, did you change them using Central Admin. If not, that is a problem
since these passwords need to be in the Configuration Database for
SharePoint.
2) Make sure that the accounts each are DBO of the content database
for their respective Web applications.
3) For AD, they should be a member of the Local administrator's
group on the WFE servers. Other than local admin they should also be a
member of the WSS_WPG group on the WFE.