I tried Purple Majesty for the first time this year, with rather unspectacular results. To be fair, none of my potatoes did extremely well this year, but the purple variety barely yielded anything above what I orignally planted. I should also note that I grow all of my potatoes in containers (like SmartPots).
Of the red variety, I've had my greatest success with Caribe (and they have a slight purplish tint to the skin). The productivity is good, it's a beautiful potato with the purplish-red skin and white flesh. It also seems to keep fairly well.
