Yes, you can certainly use red potatoes in this recipe. Red potatoes tend to be slightly sweeter than yellow so they will slightly change the flavor of this potato salad.