Either their node is down or the nodes you have channels to don't have a good route to their node.

That's my guess.

Maybe add another channel directly to their node.

Maybe look at logs if you have any to see what routes are failing.