would "eu te contei muitas vezes" be correct?
Yes, but I think they wanted "have told" to be like an "yet/already", but as they also mark "Eu te disse muitas vezes" as a right answer I think yours should be accepted too.
Would 'eu ja te disse muitas vezas' be correct also?
"vezas" no, vezas doesn't exist. :) If it was "vezes" it would be right.