1. Новое соединение - новое правило NAT.
2. Провайдеру скорее всего не хватает ip адресов и они выпускают пачку пользователей с определенным диапозоном адресов.
3. Попробовать завершить соединение, причем завершенным оно должно считаться на железке провайдера, где происходит NAT. С установкой нового соединения скорее всего попадете на новый ip адрес.