Sounds like a permission error for the temp directory Outlook is using. I have a few questions for you that should help you track down the cause of your issues:
What security level are the terminal services users on that machine?
What are you using for your temporary file folder (different for each user?)
When logged in to terminal services can you write to the temp folder?
When you say a few of your users can you be more specific? Are they all on the same OS – same config?
When you say log out of Outlook do you mean log off of exchange or exit the local outlook?