Error opening Outlook 2003 under Terminal Server user session

I've just recieved a brand new server from HP with Windows Server 2003 R2 loaded on it. This server is to be used as a terminal server for our employees working outside our office. However, I've run into a problem once MS Office was loaded on this machine. Whenever a user opens up Outlook, an error message pops up saying "Failed to start the Expression Service. The Espression Service may not be installed. This problem may be resolved by using Detect and Repair on the help menu, or by re-running Office 2003 setup." Obviously the first thing I tried was doing exactly that, which didn't work. I do know that if a user has local administrative access to that computer, the error message does not pop up. Any thoughts on getting rid of this message for ordinary users would be greatly appriciated.

What's somewhat strange is that our existing terminal server has the same software loadout, except it didn't come with the HP software, and it's Windows 2003 w/SP2 instead of Windows 2003 R2.