I am able to do the lose fat/build muscle thing on Primal. Are you *strict* paleo or do you follow Primal? As in, able to have some dairy, nightshades, etc. There is a difference and it will make it much easier on you if you are Primal. If you are lifting regularly, eating paleo/primal and can tolerate dairy, I would suggest GOMAD as it does work.
The best way to gain muscle (not strength or performance based) for me has always been high rep/high volume even on the big 3 lifts. Usually 4 to 6 sets of 10-14 reps of everything. I did get stronger, but not as strong as doing 5 sets of 2 to 4 reps of extremely heavy weights. That's just me though, you will have to test things out and figure out which one is best.
People too weak to follow their own dreams will always try to discourage others.