Nachdem ich mein Linux-Mint komplett verschlüsselt neu installiert habe, fand ich doch noch eine Lösung.
Die folgenden Packages müssen installiert sein:
------------------------------------------------------------------
sudo apt-get install openvpn bridge-utils
sudo apt-get install network-manager-openvpn
sudo apt-get install network-manager-openvpn-gnome
In meinem Linux-Mint fehlten die "bridge-utils".
Soweit ich das verstanden habe, wird die Verbindung während des Systemstarts versucht früh aufzubauen, wohl noch bevor der eigene User aktiv ist. Daher sollen die Internet- und VPN-Verbindungen so konfiguriert werden, dass sie allen Benutzern zur Verfügung stehen. Außerdem soll das VPN Passwort für alle Benutzer abgespeichert werden. Auf einem Rechner an dem man nur selbst arbeitet ist das sicher kein Problem. Wie das für ein echtes Multiusersystem zu beurteilen ist, da bin ich mir nicht so sicher. Sorry, für die schwammige Aussage, aber die Abläufe während des Systemstarts kenne ich nicht im Einzelnen, und diese Lösung habe ich auch nur aus den Informationen im Internet zusammen gestoppelt.
PS: Es ging bei dem Thema eigentlich darum, daß meine Internetverbindung nicht mehr automatisch aufgebaut wurde, nachdem ich das VPN konfiguriert hatte. Ich dachte die Fehlermeldung in der Überschrift des Threads sei die Ursache. Daher die etwas irreführende Threadbezeichnung.