Any ideas on how I might proceed to debug this?

Not without more details:
1. Are you using the lastest versions of 'threads' and 'threads::shared'?
2. What version of Perl are you using?
3. What OS are you running undeer?
4. What other modules is your program using? This is very important as many modules are not thread-safe. I suspect this may be the most likely cause of your problem.
5. Can you generate a small, self-contained sample program that demonstrates the problem?