You could plug a few days of your current diet into fitday to see what kind of calorie intake you are getting now, then shoot for a similar amount with paleo foods. You -will- lean out. Seems like most people I've got started on it over 200lb lose about 10lb of water in the first week.
Low(er) carb paleo will often slow muscle gain because of the really tight control of insulin, which someone pointed out in another thread is a VERY anabolic hormone. I fought with this for months, having trouble even maintaining weight on what should be a 500 calorie/day surplus. But then, I'm very lean and have always had a high metabolism. One week into 1/4-1/2 gomad and I'm already putting on appreciable weight. I guess I can thank the big insulin dose that milk provides for that that (and the increased hunger, ironically).
How are they checking your insulin sensitivity? I think Robb mentioned the usual test being pretty worthless in a recent podcast of his.. i think I recall him saying that your A1C is a far better indicator of what is going on.