The Mazda Tribute is a twin to the Ford Escape, many of which have also experienced transmission failures. Ford stopped authorizing towing 4 wheels down of Escapes built after 2/28/2012 but is still honoring the warranty of those built before that date.
What did the Mazda dealer tell you? One solution is to have a lube pump installed. I understand that Ford has paid (or partially paid) for the installation of Remco lube pumps on some vehicles which have experienced transmission failures.
You can search other threads on this website re: Escape transmission failures for more information.