This problem was introduced by a security update. It appears to be an issue between a network pref and the keychain. It gets fixed if the appropriate entry gets resaved in the keychain. I fixed it on my system a year ago. Two possible solutions most commonly fix it (the first one did it for me).
Solution #1: go to System Preferences -> Date & Time -> the "Set Date and Time Automatically" checkbox. Whatever it is set to, click it. After a moment, click again to return it to whatever you normally have it on.
Solution #2: use the Require Password item as AKcrab suggests. Then, go to System Preferences -> Network -> Configure -> PPPoE tab. Uncheck box to "Save Password". Retype in the password. Recheck "Save Password" box. If you have a PPPoE password specified on more than one network port, repeat the above steps for each port. When done, return to the Security prefpane and uncheck the Require Password option.
Once I fixed it on each of my systems, the problem never returned.
The solutions I found turned up in this Apple Support
thread. They discuss other options, such as checking / unchecking the Network Time option in Sharing as well.