Hm... seems like I need to restart my game. Or at least go back to my "day 1 save".
Now, for some reason I can't pay tribute. I can concede defeat, but the "+" is greyed out, so I can't offer any. Might be because I play 5.2.
I had to bounce back and forth assaulting Trebizon when they take it until they got bored and started to offer terms.