У меня такое же было на MTS-GPRS ,увеличил таймаут tls-timeout 120, стало нормально
Пробовал делать 240 ,мне показалось что openvpn его не взял, не захотел соединяться (с тойже ошибкой), откатился на 120

С другими провайдерами не пробовал

>не первый раз пользую OpenVPN для связи виндовых клиентов c FreeBSD сервером,
>для связи FreeBSD рутеров, за Natом, прокси и т.д. и т.п.
>
>Протокол TCP. для унификации использования.
>
>Но вот небольшая проблемка выявилась - через сотовиков (МегафонСПб и Скайлинк) не
>работает.
>Затыкается на этапе диалога tls-auth.
>увеличивал таймаут - не помогло. поиски в инете не дали резутата .
>Куда копать и что смотреть?
>Те же самые ключи, настройки и клиенты по обычному модему работают, а
>тут никак.
>
>в логах вот что:
>
> Authenticate/Decrypt packet error: packet HMAC authentication failed
> TLS Error: incoming packet authentication failed from xx.xx.xx.xx
> Fatal TLS error (check_tls_errors_co), restarting