I suspect that one of two things is happening: either a) your SAM header (which will be unchanged by samtools) says that your BAM file is coordinate sorted (or unsorted) after your sort procedure and BEDTools is noticing this or 2) you have orphan (i.e. unpaired reads) and BEDTools is using a naive pairwise iteration that does not account for intervening orphans.
I can discount 1) by looking at the source (confirmed by experiment).
I can confirm 2) by experiment. I removed a single member of a pair of reads in a name-sorted BAM file and obtained the same error message from bamToBed as you did.
So I suspect that you have orphans that you need to remove.
That's right, the current version expects alignments to come in pairs. I've not yet implemented logic for interleaved orphans.