@Kathryn Scofield, Error 86's in a Terminal Server environment....I fought with this issue for 4 months. IT guy said MAS issue - no error messages in MAS though - other than these Error 86 - Unlock Region Failure(s). After an all-out war broke out IT guy finally tried setting the time on the Kerberos ticket to 18 hours. Eliminated the problem and haven't had it since. Weird thing is....another client had it on a Windows 7 workstation to a Windows 2008 Server without Terminal Server involvement. IT did not understand what I was saying at first, so issue continued until they had some data corruption. Then COO became involved. IT guy then got his boss involved, Kerberos time changed and no problem since (knock wood!)
For the Paperless Office issue - did you reset all paperless paths using UNC now that you have Terminal Server involvement?