I managed to find a fix for the issue. The following answer is meant for Thunderbird 17.0.6 in Ubuntu, but might work in other versions / OSes as well:
- Unsubscribe from the offending folders where the error happens
- Compress / condense your folders
- Re-subscribe to your folders (you can press space to select all visible and marked folders)