What is meant by Physarum polycephalum having 720 sexes?
It is true that many/most unicellular organisms such as e.g. bacteria or fungi have no need for sex to reproduce, and can divide by simple cell division. However, sex (defined rather broadly) is a universal feature of life. For example see this review article by Rosie Redfield, which examines exactly what we mean by "sex". The broad definition is just recombination of genetic material, which is a universal (or nearly so) feature of organisms.

It's a little hokey to say that Physarum polycephalum has 720 sexes, as "sex", the idea of a specific category of individuals with regard to reproduction, is different from the biological idea of "sex", when we say "yeast have sex". 

What Physarum has, like fungi and other similar organisms, is not really sex, but mating type (see here). Mating type really has nothing to do with what kind of sex organs a fungus has, but rather what fungi have sex with. Certain mating types only have sex with certain other mating types. But this isn't really a one-to-one correspondence like male-female. It's much weirder than that.

There are both "heterothallic" (sort of "single-sexed") and "homothallic" ("hermaphrodite") mating types of the protist, and each organism has a mating type. The homothallic ones don't need other individuals to have sex and make offspring. The heterothallic ones do need other individuals. These mating types are defined not by a sex chromosome like in humans, but by a single gene. When they say 720 sexes, what they mean is that we have found 720 different DNA sequences at the mating type gene which have somewhat different mating behaviors. 

I think that your evaluation is correct that the journalists are being pretty inexact here. But I think also that it's important to recognize that basically all of biology is sexual, one way or another.