Была такая же проблема. Я просто написал в саппорт твиттера с того email (если точнее, то указал его в форме), который был раньше у меня был раньше. В течении нескольких дней все восстановили.
Но. При восстановлении я тоже столкнулся с тем, что пишут про The email address you're writing from does not match the email (бла-бла-бла). Оказалось, беда была в Яндексопочте. Твиттер был зарегистрирован на @ yandex.com, а письма уходили с @ yandex.ru. Проверьте, может быть, у вас тоже самое (не обязательно Яндекс, но все равно посмотрите)