The reconnect at logon has been selected for the network drives, however the users of the network cannot reconnect at logon, but the administrator can. How is this possible, does it have anything to do with permissions?

Is this a new problem? Were things working OK previously? Any new hardware and or software?

Permissions would be listed here:

click Start/Run and type gpedit.msc