I agree that the Paleo population is growing and people are listening. I feel this way based on the number of inquiries I get about Paleo on Facebook. It's not a LOT, but it's a larger number than I would have ever expected.
I believe in evolution. I do not believe in God or any portion of religion there-in, but not because I'm atheist... more because I believe in science and have a really hard time believing in anything that can't be proven. I guess what I actually lack is faith...
I also believe that it will never go mainstream because the government isn't going to accept it because there's no money in Paleo. I agree that we'll be slotted next to vegans... however, I believe the medical community will start to adopt it - not big-pharma, but the medical community. I learned of Paleo from my one of my chiropractors and later learned that another chiropractor of mine (see each for different skill sets - one to adjust my spine, one to perform ART) and my osteopath are all paleo. Once my doctor said she was Paleo and started recommending Paleo readings to me, I was sold. The second chiropractor's involvement got hubby on board - he's about 75% paleo at this point.
So, I believe in time it'll get better and become more recognized... what I hate is that it gets coupled with Atkins as soon as anyone mentions no bread or low-carb.