If you go into the Network Connections folder while logged in with your own User Account and double click the internet connection to start it, there should be an option to select -
Save this Username and Password for the following users:
- Me only
- Anyone who uses this computer
Select the 'Anyone' option and then connect so that the setting is saved. See if that allows all users to connect themselves.