I can't remember all the details. (I am at work at the moment and this machine only has one user my machine at home has several and is set-up so that they can all access the internet).
I think what you need to do is look through all the internet settings and somewhere you should find a check box something along the lines of "allow all users to use this connection".
Sorry if this is a bit vague, but at least it will bump you up the list! - When I get home later tonight I'll have good look and if this thread is still going give you chapter and verse!