Clone war of the sexes
All of the parthenogenetic species with which I'm familiar are female. Females, obviously, have all the machinery for reproduction in place, and all they have to replace is the function of one itty-bitty little sperm, while for a male to reproduce without females, he'd have to replace the functions of big, well-stocked eggs and uteruses or whatever equivalent organs the mother of the species has at her disposal. It's hard for males to get around the female contribution to reproduction. At last, though, one species of fire ant has shown a way to do it, not that I'd ever want to go down this particular road.
I'm going to expand on this strange genetic pattern John Wilkins described. First, though, here's a little background on haplodiploid sex determination.
In mammals, we have a familiar sex determination system. We're all diploid, or possess two sets of chromosomes, and we produce haploid gametes, sperm and egg, that fuse to produce a new diploid. All female gametes have one X chromosome, and males produce two kinds of gametes: one kind also has one X chromosome, and the other has one Y chromosome instead. At fertilization, if the female gamete fuses with an X-carrying sperm, it will have two X chromosomes and develop into a female, and if it instead gets a Y chromosome, it will have one X and one Y and develop into a male.
Some insects, specifically most species of the Hymenoptera, do things differently, with a sex determination system called haplodiploidy. Males are always haploid, having only one set of chromosomes, and they produce only one kind of gamete, and all of their gametes are genetically identical. Females are diploid, and produce haploid eggs. If the eggs are fertilized by a male, they develop into females; unfertilized eggs develop into males. Fathers can only have daughters, and mothers produce sons without the contribution of a male. Males don't have fathers, literally.
Here's a diagram from the Nature summary that might help clarify all that. The paternal gene set is blue (remember, he's only got one!), while the two maternal gene sets are colored pink and red.

The pathway labeled "a" is what happens if the pink or red gamete is unfertilized: it produces a haploid male with only his mother's genes. The path labeled "b" is fertilization, and all of the progeny are diploid and female.
In social insects, most of these diploid females become sterile workers ("d"). Some of them will be changed by environmental factors to become repreductive females, or gynes ("c")—in bees, for instance, larvae fed "royal jelly" go on to develop their reproductive potential and become queens. Insects that use haplodiploid sex determination are predisposed to develop social systems, because of another quirk of genetics.
Pick any female in this system. Half of her genes are blue, coming from her father, and half are red or pink, coming from her mother. The degree of relatedness of one individual to her mother is ½. This is also true in us; half your genes come from your mother, and half from your father.
We can also calculate our degree of relatedness to our siblings. In humans, we get half our genes from our mother, but which half is random. There is a 50:50 chance that any one maternal gene I carry is also shared with my brother; the other possibility is that he inherited the other maternal gene. The same is true of the paternal gene set. The average fraction of genes shared through common descent between two sibling mammals is:
You are just as related to your brother or sister as you are to your father or mother.
In haplodiploid insects, it's different. The father only has one set of genes to pass along, so the probability that an ant will share the same paternal genes as her sister is 100%. So the degree of relatedness for two sisters is:
A typical female ant is genetically more closely related to her sister than to her mother or her daughters. Hamilton proposed that this increased the incentive for cooperation, and was one of the factors in leading many of the Hymenoptera down the path to eusociality.
Fire ants, Wasmannia auropunctata, have added another twist to this pattern. Fournier et al. analyzed the relatedness of queens, workers, and males in multiple nests in French Guiana, and found that all of the queens from a colony had identical genotypes—they were clones. Similarly all of the males from a colony were clones of each other, and most surprisingly, they were not related to the queens. How to explain this? These fire ants have developed new paths of reproduction.

First, the queens are capable of reproducing parthenogenetically, pathway "e". They presumably suppress one of the meiotic divisions to produce diploid gametes without any contribution from a male. This is a very bad deal for males: they have just been rendered completely superfluous. It's also a bad deal for the workers in the colony. Remember, the incentive for sociality is that all of the sterile worker females are related to ¾ degree to the next generation queen, but now they are only related to the ½ degree to the parthenogenetically produced queens. To make a bum deal even suckier, the queens also seem to have evolved genetic mechanisms to suppress gyne production from the ranks of the diploids produced by fertilization (the big X over pathway "c"). Can you say "exploitation of the working class"? Sure.
Oh, well. What can you expect? Fire ants are evil.
Notice that the males are still needed for one thing, though: production of sterile workers. Genetically, they gain nothing from this. The male lineage would hit a dead end at this point, since none of their progeny would ever reproduce. They've hit on an interesting solution, though. Something in their genome is capable of eliminating the female gene set, kicking out the maternal chromosomes and producing haploid individuals after fertilization (path "f"). Male genes now have a way to make it into future generations.
The net consequence, however, is that males and females of this species have become genetically isolated and represent parallel lineages that do not mix, except in the production of a sterile set of workers in each generation. Males parasitize the queen's eggs to make males, and queens exploit the labor of the workers to produce new queens.
I am not a population geneticist*, and some of this stuff is hard for me to grasp. In particular, I couldn't see why the fire ant would also shut down the normal pathway ("a") for making males from the maternal genome. David Queller offers this explanation, though:
Strange patterns of natural selection might also explain why two standard modes of reproduction have shut down. First, why would queens give up producing males by the normal pathway (path "a")? As the system stands, there is no selection for queens to produce males. A queen who produced males gains no advantage in her own (female) gene pool; it is like putting her genes in another species. I suspect that similar logic applied, although with less force, when the female and male pools were only partially separated. The lower value of putting genes in the male pool would select against females doing so.
J.B.S. Haldane was right. "The universe is not only stranger than we imagine it to be, it is stranger than we can imagine it to be."
*Which leads to one caveat I have. The research is done by sampling the genetic characteristics of ants in multiple colonies, and the novel mechanisms of reproduction mentioned are so far inferences only. I'd like to see experimental demonstration of male clonal reproduction a little more directly…but that's because I'm not a population geneticist.
Fournier D, Estoup A, Orivel J, Foucaud J, Jourdan H, Le Breton J, Keller L (2005) Clonal reproduction by males and females in the little fire ant. Nature 435:1230-1234.
Queller D (2005) Males from Mars. Nature 435:1167-1168.


So, if through some accident or infection, all the males of a colony died off, would the colony continue with just females?