My local supermarket is big, and close by, but its vegetable selection leaves something to be desired: it tends towards the wilted and entombed in sealed plastic, rather than the crisp and breathable fresh that I would prefer. I have been frustrated with the parsnips of late - one of my favourite root vegetables to roast - because they come in a motley bunch of large-and-small specimens encased in a plastic bag, and everyone knows that big parsnip roots are woody and fibrous. So when I saw, further down the display, four evenly matched carrot-sized white tubers gathered together by an elastic band, I grabbed them with glee.
We had a bit of a kerfuffle at the cashier, though, as she didn't know what they were ("parsnips", I said) and didn't have parsnips on her list of codes; the code her fellow cashier gave her came up as "parsley", which I said wasn't right. A flunky was dispatched for a price check, and returned confirming it was indeed parsley. We had a closer look, decided that the attached greenery did indeed look quite parsley-like, and rang the things through. A new vegetable. Cool.
A quick google search confirmed that many North Americans have made the same mistake as I had, coming home with what they had thought were parsnips, but weren't. Also known as turnip- or parsnip-rooted parsley or Hamburg parsley (and scientifically as Petroselinum crispum var. radicosum, apparently), parsley root is common in central European cooking, where it is used in soups and stews; the leaves can be used just like regular parsley.
So what's it like? I have roasted and braised the parsley roots I bought, as well as added them to mashed potatoes, and found they taste like a cross between parsnips, carrots, and celery - slightly sweet, with a pleasant vegetal undertone. They cook up nicely, without the woodiness or dryness that you can sometimes get from parsnips or certain varieties of potato. They can be grated and added to meat loaf and dumplings, and can also be eaten raw, chopped into salads; in this form they have a nice crunch and more pronounced parsley flavour. Saveur, for example, has a recipe for a chicken and parsely root salad (http://www.saveur.com/food/classic-recipes/chicken-and-parsley-root-salad-49136.html) that looks quite tasty.