Could this be because pins 2 and 3 (used very often in the soft serial examples I've seen) share an interrupt with the UART on pins 0 and 1? Unfortunately, my device requires a specially designed shield so I can't move pin assignments around easily, but if someone who is having interrupt problems could try using, say, pins 8 and 9 for the soft serial and see if they continue to have problems, that would be an interesting experiment.
I was using pins 2 and 3 and have changed them to 8 and 9 as suggested - unfortunately there is no noticeable change in the lockup.
Really hope this can be resolved.. 