Hi Nick,
I have a few ideas on this. First, when you installed Office on this computer, did the installation give you an option to configure the software for a single user or for all users of the computer? I have seen installers on Windows 2000 and XP do this, and maybe your installation is not an "all user"-friendly installation. If that doesn't help, you may want to check the Office documentation (or the Microsoft support website) to see if there are any user-specific settings in Excel that you need to enable for all users.
I hope one of these suggestions points you in the right direction. Good luck!
-D