The only way I have found is the Cueler App which has a relevant setting:
However, new uploaded videos are still not shared on the fan page and I cannot reproduce why.
Are there any alternatives that I could try?
This IFTTT recipe Post YouTube upload to Facebook Page should do the trick. You'll need to create an IFTTT (stands for If This Then That) account if you don't have one and add your FB Page and YouTube as "channels" but that's not nearly as difficult as it might sound and you'll be able to customize formatting etc. for posting your vids to the page, among other things.
If have found that IFTTT recipies like this one, does have some limitations to the autosharing of youtube videoes. I ran into the problem of autosharing scheduled videos. IFTTT support confirmed this for me when I contacted them.
If you want your video to be published at the same time it is uploaded, there's no problem in using IFTTT, but if you (like me) want to control when you video goes live, and don't want to sit at the computer to upload the video at this specific moment, scheduled publishing is a must.
Scheduling requires you to be a YouTube partner, see how to become one here. Do not mind that he says that monetization is different from being a partner, you will have to turn it on to become a partner.
The free service Zapier, on the other hand, can solve this problem for you. I modified this zap a little and it works like a charm. (I modified it because it was tailored towards pages, and I wanted to use it for a normal Facebook user).
I do not know how the mechanics of each service is set up, but I think the reason why Zapier handles the scheduled videos well, is that it checks a specific user every 5th minute, and doesn't rely on some kind of trigger from YouTube.
I do not know if IFTTT will support scheduled publishing in the future, but at the moment Zapier seems like the best solution if you want to be able to use scheduling in the future.