Непонятно с чего бы провайдеру блокировать тоннель - никогда с таким не сталкивался, скорее всего просто технические проблемы.
А так - посмотрите в сторону
SoftEther их фирменный протокол работает через SSL по стандартному порту - в общем обычный https трафик.
Да и вообще - чем вам SSH не угодил? Вместо VPN сервера поставьте SSH сервер, и нехай эти убунты по SSH к нему коннектятся. Тот же VPN по сути.