Hello, i seem to keep having the same issue, when i need to color fondant a color that takes alot of color to achieve meaning i have to also work it alot longer, the end result is way to soft. I even started making it several days in advance so that i would have time to let it set up and it doesnt help. 

I do use vegetable shortening when coloring to keep it from sticking, which im sure is what is making it soft, I am just not sure what i should use to fix that. 

Should i add corn start or food coloring or tylose powder?

Please help! 

I would knead in a very small amount of tylose--a scant 1/4th tsp./lb.--and then let it rest for 24hrs., reassess.  Shortening actually dries out fondant, but some colors have glycerine in them and that makes fondant softer.

Ok so it is most likely the coloring itself that is making my fondant soft? 

Its the biggest issue when im coloring fondant to cover a cake, its so soft that it tears while im covering 

I will have to try adding a little bit of tylose after creating a color i have to use alot of Gel for. This time i needed a deep bright red so it took alot of working and alot of gel color to achieve. 

Are you making your own fondant?  Is it very soft to begin with?  If so, adding tylose to get it to the point you like would always be a good idea.  And, once you add color, it's likely a necessity.

If it's premade fondant, the gums vary and some are soft to start with [I find FondX and the new Wilton to be that way], and I add tylose to them.  Others are "tighter" and take color OK without adding gums to them.

For deep colors like black & red, I buy premade.  I find that it saves time, money, & frustration.

If I need a deep color, I save myself the hassle and purchase it pre-made (deep red, black, etc). For most colors I use Wilton fondant and it's fine. I do add some shortening but in small amounts to make sure things don't get too soft. 

Shortening is a blessing and a curse.  I roll out on it--a smear on food safe vinyl [The Mat by Sweetwise], but I never add it into the fondant.  It actually can change the balance in the fondant and too much will cause it to crack and be dry--go figure.  It stops the fondant from holding together properly once you get a certain amount of it in the product.

one other particle of information is that i let my fondant air dry a little and knead it in -- and repeat as necessary -- especially for large deeply colored amounts that will be cake coverings -- for modeling i add copious amounts of cornstarch

Yea i typically use Wilton fondant, and the only time i use shortening is when im coloring because it keeps it from sticking to my hands. When rolling it out i do have a Mat from sweetwise that i love. I might just try and buy the black and red from now on, they are the 2 that end up the softest. 

I will try adding some tylose next time and letting it set up and see if that helps! 

For Red & Black, I premade, but for other colors, I take about 3/4 of the white fondant, color it with a lot of coloring all at once.  Use shortening for help.  Once you get the color you want, add the 1/4 white piece and mix that in.  It helps with alleviating the softness, but keeps the color.