[VSerge]

Проблема была в том, что на файле "телефонной книги":

C:\Documents and Settings\All Users\Application Data\Microsoft\Network\Connections\Pbk\rasphone.pbk

стоял атрибут "только чтение".

Как только я снял "галку" в чекбоксе - проблема была решена; я смог удалить ненужные соединения.

ps. Проблема выяснилась после того как я пытался установить соединение PPPoE - "Невозможно обновить файл телефонной книги." Стал "копать" - и проблема решилась.