Which publications actually count for tenure? I have been told in no uncertain terms that papers published with your PhD advisor simply Do. Not. Count. when it comes to tenure. Quote: "Publications with your advisor will be crossed off the list."

An assertion that strong makes me insecure about collaborating with any senior researcher.  Will these publications also be tossed out?  How senior is senior?  For instance, suppose I collaborate with junior faculty at another institution who was hired at roughly the same time.  Will outcomes from that collaboration be deemed "more significant" than with, say, a full professor from that same institution?  And what about the field?  Am I "safer" publishing with senior people from a different field, because there will be an easier perception that I am "carrying my weight?"  Or should I simply avoid collaboration altogether, and publish exclusively with my own grad students and postdocs?  How do the real discussions go, from those who have actually been in the trenches?

Honestly, I would much rather just collaborate with the people I do the best work with.  (Isn't that the best thing for the field anyway?) But I am terrified of having years of good work "crossed off the list" because I did not pick the right dance partner.
I can't speak for your field or institution, so take anything I say with that in mind. 

That being said, in my experience (in computer science, at a well-ranked private university) what matters is not so much who you collaborate with, but that you have a research agenda that is strongly identified with you (as opposed to your senior coauthors). If all of your papers are coauthored with the same senior researcher, this can look bad, because it can be difficult to disentangle your research agenda from his or hers. But if your papers have a cohesive theme, and are coauthored with a variety of other people (even if many are senior), this is great. 

So in summary, in the parts of academia I have seen, you should collaborate with whoever you want to, but make sure you have your own research problems and are not just working on your coauthor's problems.