Given that Tessio and Clemenza didn't know that Rocco had built up a secret regime, and given that they had no clue that Michael had a plan to wipe out all the heads of the other families at the time, the Corleone family appeared weak. as Moe Greene surmised they were being run out of New York, and they didn't have the muscle to deal with him, let alone Barzini. Michael was still untested as a Don, and Clemenza and Tessio wanted out to form their own family but were denied that permission. On top of that Michael announces that the family is moving to Vegas, and that Carlo was going to be his right hand man. Tom was declared "out." Now Tessio and Clemenza both knew Carlo was a traitor who set Sonny up, and even if they knew Tom was not the greatest wartime consigliere, they knew he could be trusted and that he brought a lot of knowledge and skill to the table. Oh, and Vito was dying. To stay loyal to a failing family was not a good business move, and it was "smart" to bail...nothing personal just business. Clemenza chose loyalty. Tessio, who was always smarter did not. Simple as that.