I had a similar symptons. It turns out that in my case I was linking to macs that had the same name(makes sense since they both belonged to me) this may have caused some domain resolution issues for AppleTalk. I even had the same user on both machines! I changed this too.

Since things worked fine after that simple tweak, I am naively assuming that the name conflict was the reason.