It seems that the APN had one slight difference between ROMs that worked with LTE for me (older CM, stock TW, GPE), and ROMs that had no LTE or eventually dropped LTE (CM12.1 based). The bearer was not set to LTE in the APN profile for the ROMs that do not work for me. Changing that quickly fixed the problem (figuring it out took me much longer). I looked around a bunch when I had this issue, and found people with the same issue, but no solutions. So, that's why I post this here now. Here's the How To if needed:
Go to Settings, Mobile Networks, Access Point Names, and Sprint LTE internet.
Scroll down to Bearer and see what it is set to. Mine was Unspecified, and that's what was causing the issue. Set Bearer to LTE
Go back to APNs, and also set Bearer to LTE on Sprint EHRPD internet. I know that's not the normally selected APN, but if you only change Sprint LTE Internet, it seems to automatically change to this EHRPD one, and it still doesn't work.
That's it for now. Enjoy your LTE again on 5.1.1. It seems to be much smoother.