Oh, no, it has the codec. On a clean install of Debian it plays pls files JUST FINE. It downloads them and totem plays them. Perfectly.
After I "upgrade" my OS, Firefox is updated and still downloads the pls files. It's Totem that stops working. I dont know where I would find a codec that is most likely built into it.