I've had this same problem, backing up both with PIM Backup and with PowerSMS. That it happens with both seems to point to the problem being something fundamental to the way messages are timestamped/sorted, and how they get reinserted into the database from a backup.
Here's a thread from xda that seems to suggest it's fixable. The most promising idea seems to be to wipe the sms box clean, and then turn off threading -> restore -> turn on threading. (I, like you, tried turning theading off and back on, but the messages were already inserted at that point.)
http://forum.xda-developers.com/show....php?p=2663807
Of course, post #1 in that thread also says that if you use powersms you don't have to worry about it, and that isn't my experience. (I might be using an old version, though.)
I'll probably play with it next time I flash a rom, but I don't care about misthreaded sms that much until that point.