As an administrator you checked out master page either via SharePoint designer or from Pages Library in publishing site in MOSS 2007. And suddenly all the users who had access to the site just fine starts getting access denied messages.
Make sure you check in master page to resolve this issue.
There are other possible reasons for access denied message -
Even though master page is checked in users are getting access denied message but as an admin you can login fine to the site. This can be caused by a custom control on the Master Page or page layout or a web part that tries to accomplish things that are beyond logged user's access levels. Make sure you analyze simply by removing web parts first and if this does not resolve then remove custom controls or custom code blocks from the master page.
Hope this got you moving further!