Excel 2003 hyperlink problem with network

Built a spreadsheet for a company. They are running a Microsoft small
business edition server. When creating hyperlinks in excel they’ve
found the following problem: “as long as the linked file is on the same
drive as the excel file, or a removable external hard drive the links work.
As soon as it is to a separate partition or drive it fails.”

The network admin says everyone has read/write access to all the
shares without restrictions. Any ideas why the hyperlinks to the shared
drives aren’t working?

Suggestions would be much appreciated!