eat more? for starters, make sure you are eating adequate protein and fat. then add carbs. i mean, primal/paleo isn't low carb. so crank up the carbs. plenty of potatoes, sweet potatoes, fruit, white rice, etc. as long as you are active (it isn't baseball season) this caloric surplus should be exactly what you need to slowly put some muscle on
i think a lot of people struggle with this idea that paleo/primal is a "diet" for weight loss. it really isn't. its about optimizing health. so by eliminating those nasty things, you were eliminating the extra calories you were consuming. thats about 90% of why you lost weight. if not more. you need to replace those calories with more of the good stuff, lift some weights, and add some of that lean muscle mass now. some people like to start with a 500 calorie a day surplus in order to add mass. then they fine tune that number depending on how much fat they are gaining. if you're adding too much fat too quickly, then eat an extra 300 calories a day. if you 're not adding fat, try 600-700 calories a day.
I have a lot of hard miles on my body from before I realized I'm not 100% invulnerable. Now I just think I'm 75% invulnerable. -Mr. Anthony