I used Yukon Gold because the recipe specifically said Yukon Gold.
I like the idea of new potatoes. I may try that.
This particular recipe had very specific methods. It was all Dutch oven cooking. The meat was browned but only when cut in three big pieces. The smaller final cubed phasebof the meat was not browned. Vegetables were placed in the beginning to stew but then fished out after the first hour in the stove. The vegetables that would be in the final product were put in for the next hour along with the potatoes. It was a lot more labor intensive than throwing everything in a pot but I loved the flavor.
This recipe has wine and anchovies (or fish sauce).
Here is the actual recipe and instructions for anyone interested.
Bay leaves, you did not mention how many bay leaves.
They are important for good stew.
We made that exact recipe last month. Except we used red potatoes. 
2 bay leaves. Very important to a good Sunday sauce.
How did you like it? Both of my daughters liked it and that’s always a good measure of success.
Potatoes and some other vegetables can develop persistent hardness if they’re cooked too slowly. If they’re heated to between 130 and 140 F for 20 to 30 minutes at the beginning of cooking, they’ll never get soft after that no matter how much you cook them. Is it possible that this happened to you?
You can always dump the potatoes in favor of Barley as a starch. Barley that has hydrated on Beef stock is awesome, much better than boring old Taters in beef stew.
I will have to respectfully disagree with you.
I completely agree. We often eat an Indian lentil dish. And when we do, we make “glop” the next day. Glop is leftover lentils with some barley and beef broth added. The barley is mostly hydrated by the beef broth, and is fabulous.
Loved it. Will be making it again soon if the temperature ever goes down to “winter.”
wolfman - Barley is for beer. And maybe soup. But a stew demands potatoes.
There have been lots of times when I made stew and I either had run out of bay leaves or forgot to put them in. I can never taste any difference. But I still use them! 
I brown the meat and then put in my onions. After they soften a bit, I add my other ingredients and let it all hang out together.
The Soup Nazi couldn’t make soup this good on his best day. This is one for the ages, IMO.
I’ll be honest: I try to put in bay leaves as a matter of course usually for soups and stews, but at least half the time I don’t, and I really cannot tell the difference in taste. Bay leaves just don’t taste like anything to me. Putting them in has really been more ritual than anything for me. Rosemary, thyme, oregano, marjoram, etc. – all those I can pick up in the most minute levels in a soup or stew. But bay leaves? I still have no idea what they taste like. (Actually, not 100% true. A doper a few years back sent me fresh bay leaves from her tree, and they actually had some kind of flavor to them. But the dried ones I get, no matter how new, while they do have a scent to them, don’t seem to impart any flavor I can detect.)
Ah, I didn’t notice it was the Serious Eats recipe. I’ve made it verbatim a few weeks ago, but it took a good deal longer than in the recipe. The meat took about 2 hours, not 1 1/2 to get tender, and the carrots and potatoes were the better part of an hour, maybe a little more. I can’t remember exactly. If you read through the comments, others have the same experience. It could be the calibration of our ovens, it could be the meat or potatoes themselves. Just use your senses when cooking. Stew is very forgiving. If the meat or potatoes are not tender, just keep cooking until they are.
I make a crock pot pot roast kind of thing, where I cook a hunk of beef in beer and onion soup from a packet. We love it. But I always have a lot of the “juice” left, even after making gravy.
So I had a big container of the juice in the fridge, with thoughts of what can I do with this and since I was making beef stew anyway, I used that instead of plain water. It was amazing. Beefy, oniony goodness.