Nightshades are conjecture too...I get someone on Paleo and "no nightshades" and their health improves, pain decreases...every time. Oh well.
Starchy veggies would seem to fit Paleo just fine, especially with what Darryl Shaw posts up here so often.
I put it this way...we know that humans made it this far on "Paleo" foods...everything after that is suspect (but could be okay, Weston Price's work with different cultures would seem to show that).
Maybe the nutrient content research here
should simply be ignored if one doesn't want to "believe" it.