From the University of Pennsylvania museum of archaeology and anthropology -- 
http://www.museum.upenn.edu/new/exhibits/online_exhibits/wine/wineintro.html

<<If winemaking is best understood as an intentional human activity rather than a seasonal happenstance, then the Neolithic period (8500-4000 B.C.) is the first time in human prehistory when the necessary preconditions for this momentous innovation came together. >> [There's much more to read there]

Seems like wine is not paleo simply because it's history goes back only to Neolithic times... whether theoretically it 'could/might/wished-it-had-been-paleo' seems to be a matter for personal 'faith' and belief system.

Dedy