Were you eating a lot of wholegrains before?
I put on a lot of weight after I gave up gluten grains. I suspect I was undiagnosed celiac. I wasn't coming from a SAD when I went primal - I just gave up whole corn and legumes essentially. It led to weight loss because I had given up gluten grains a few years previously.
I love veggies too - currently eating around 8 portions a day. I get constipated when I don't eat enough.