I realise that tomatoes are a new world food but I'm not sure why you are
restricting them from a paleo point of view (maybe I missed a thread).
Solanum species are a staple of desert Aborigines and I figure solanum must
have been around for a long time (though I could be wrong).

Cheers

Sean