It looks like my provider had SMS disabled on some of the SIM cards, but not all of them. I’m not sure why, since they’re all on the same plan. I asked them to enable SMS, and the issue was resolved.
I tested one of the SIMs in my phone, and it immediately became clear that this was the problem—on a phone, you can see the SMS status right away.
Maybe Teltonika could expose this more clearly in the web interface as well? Right now, you just get an unexplained error, which makes troubleshooting much harder.