Sometimes they can - it is just a matter of applied potential and conditions. In conditions that we usually observe they don't.
But if you think about it, oxidation is just a removal of electrons - so basically heavily ionized gas contains just "heavily oxidized" substances. If the energies involved are high enough you can remove electrons from almost everything (the only safe thing is a bare nucleus).
If you take a molten salt containing polyatomic ions, as long as potential is below some level, simply nothing happens. That's what we observe in most cases, hence statement "polyatomic ions don't get oxidized" covers these cases. But if you apply potential high enough something has to give up
Simple example - sulfuric acid can get oxidized to
http://en.wikipedia.org/wiki/Peroxydisulfuric_acid. Oxidation of sulfate was even a basis of commercial process, see also
http://en.wikipedia.org/wiki/Hydrogen_peroxide#Manufacture.