I have transplanted Yucca badly (ended up with no roots!) and they have survived. I don't know where you heard that Yuccas don't transplant but obviously even pieces will survive.
Try to get as many roots as you can and be patient. It will take awhile for them to grow beautifully again but they will.
On another note: People who take down trees for a living can put them right where they want them. There is also the option of taking the dead tree down one piece at a time. If your Yuccas are part of the new planting scheme, leave them where they are.
Daisy