when you're talking full access, are you talking about share permissions or file system permissions? because they are two different things. Everyone can only access the share if they have proper file system permissions as well.
btw, if you didn't know this already, you can set the file system permission on the "Security" tab of folder or drive properties. If the "Everyone" group isn't listed with proper permissions, there is your problem.