посмотри в сторону 3proxy, компактный и легко настраиваемый прокси в том числе и под Windows. А вообще если интернет от провайдера через витую пару, то лучше для начала поговорить с ним о подключении нескольких машин на один канал (еще один ip) это может быть самым легким выходом если провайдер пойдет навстречу. А как таковая Ubuntu тут пока не причем