How do I fix a network drive mapping issue?

A few weeks ago we had to reformat our primary Windows 2003 data server. This server was primarily used for housing company data along with being the primary host for DNS, DHCP, Active Directory, etc... We had setup several shared network drives for use by various departments, individuals and a public drive for all with in the company to access. The issue we have now is that after re-installing Windows and restoring all the info from the back up tapes, we are finding issues here and there with some people being able to access the public drive that I just mentioned. Not everyone is affected however, what is happening is I was able to get most everyone re-mapped to all their drives including the public drive. Whats going on now is that if say someone decides they need to access the public drive from the conference room PC for a presentation or what not, I map it and get an access denied message, knowing that a few minutes ago they were at their PC in their office and was accessing it with no problems. As I said this has been happening like this when someone tries to access from another computer and not the one in their office. The permissions from the best we can tell hasn't changed at all everything that was on the back up tape was restored properly. As strange as this sounds could this be specific to machine and not user?