Yes, gel or paste is the right thing to use. But, as you now know, if you try to add too much, you wind up with a sticky mess. Whenever possible, lightly tint your gumpaste, then paint the item after it dries.
The balloon in this picture was tinted with red gel until it was a dull pink. Then, once it dried, I painted it with red luster dust mixed with confectioners glaze.http://www.cakecentral.com/modules.php?name=gallery&file=displayimage&pid=1434870&sub=1434873
Personally, when my gumpaste gets sticky, I don't like to add more sugar. I just add a dab of Crisco (white fat) to keep it from sticking. You will also experience less sticking if you wear foodsafe gloves when you knead in the color.