If it seems to be NIS-related, are you using nscd?  We had to turn on nscd and tweak the nscd configs or we had a lot of DNS issues.  Wihtout nscd we were seeing gethostbyname issues, although IIRC they were in torque more than the AM.