The new terminal opened a little over a year ago (I happened to be there for the opening ceremonies -- got free candy.)
At that time, the ADO buses to Chetumal were leaving only from the new terminal. I went to the old terminal where I had always caught them and had to taxi to the new one.
But some other buses, not ADO, still left from the old terminal. Guess it's possible that the ADO Chet buses have switched back to the old terminal, too.