How did you sand/shape it? I found it took me forever to get it sanded down; seems like you got it pretty quickly.
I think the key to the glue is actually sanding it down enough to make sure there is enough surface area contact between the rail and the body so the glue can grip on to it. Mine is currently held on with epoxy and it seems to be holding pretty well.
My previous attempt was with Gorilla Glue, which came apart after a while. I'm thinking paintball fill just happens to be a solvent against Gorilla Glue.