The super glue gets a skin on it the second it hits the water. So, just putting it in and pushing it onto the rock will not suffice to get it to stick. What I usually do is give the superglue a few seconds in the water (maybe 7 or 8, don't actually time it) and then put the coral in place. One you get it about in the spot you want it, twist the coral against the rock you want to attach it to. What I think this does is break the skin on the glue and allows the glue to directly contact the rock. The reason I give the glue a few seconds in the water before I try to attach it is that it seems like maybe it allows the skin to get thicker and then when it actually break it rips a bigger hole in it (I think, letting more glue directly contact the rock at once and then sticking it more quickly). Don't know if you're already doing this, but give it a try.
Also, you might be surprised by how much you actually need to use in order to get them to stick. Personally, I never use less than about 1/3 of a tube for anything but the smallest frags. For attaching most colonies and mini-colonies I'll use the better part of a tube. My biggest colonies I end up using almost 2 tubes and/or aquamend. I wouldn't recommend aquamend for smaller stuff because it drives skimmers crazy and does not cure very fast.
Finally, if you can do the gluing outside of the water, do it. Then, to get it to cure quickly, put it back into the water. Gluing outside of the water is much easier, but for some things impossible.
Don't know if you're already doing these things, but I hope that helps.