Hi Caleb,
if there were "unpaired" reads in the files, simple would not fix the problem, since these unpaired read will shift the ordering of the reads.
I have looked at the trimmomatic documentation, and it output the unpaired reads into separate files, so it should not create any problems.
So it indeed seems like a problem with the original files, and it's not simple ordering, since this would have been fixed by sorting.
The first thing you could check is whether the read IDs in the two files are consistent.
If that is true, the problem may be deeper, and I would need a small example subset.
Cheers
Alex