@Inspector I don't think the carrier would be a factor, but I can't rule it out at this point. Could you reach out to us in a private message, so that we could take down your info and delve deeper into this concern?
After completing all the steps outlined above, even clearing cache partition, I still got the same error message. However on a hunch, I reinstalled Samsung Car Mode, and Bixby once again works as usual. Go figure. Anyway problem is solved, but I have no idea how.