Your response is fine. What I say would probably depend on my relationship with the vegetarian. If they were "cool" I may just quip back "so where do you get your protein?" If someone was teetering on the edge of converting, but fearful of cutting out too much carbs you could let them know that sweet potatos and such are still paleo. If its someone a bit more knowledgeable I suppose we could discuss energy partitioning in relation to the sort of exercise we are looking at and get into all kinds of fun discussion about the need or lack thereof for any starch at all.