Ubuntu VM Boot Issues with Newer Kernels on Microsoft Hyper-V Hypervisor

I have two Ubuntu Server 18.04 LTS VM's running on Hyper-V on Windows Server 2012r2. Additionally, I have two Windows VM's (1 10, 1 7) on the same Hyper-V server. The Windows VM's have not experienced this problem.

They both exhibit the following symptoms when booted from a kernel > 4.15.0-43 (specifically 46 or 47)

The Kernel boots very very slowly compared to normal. It typically hangs for a while around this line: and eventually continues.

The next line it hangs on for a while is: followed by

After a long time, the virtual machine fails to find the virtual hard drive and boots to a BusyBox recovery terminal looking like:

I can boot off of a Linux live-cd (Ubuntu 18.04 LTS), mount the partition of the virtual hard drive and access all the files. Additionally, I can confirm that the UUID seen in the recovery terminal is correct.

This did occur after the windows server updates KB4493451, KB890830 April, KB890830 March and KB4489891. However, I cannot confirm if the Linux VM's were rebooted between the application of those updates and now. I can confirm that the problem did occur for the first time after the reboot after the installation of KB890830. (We haven't rebooted since the installation of KB4493451).

What might be the problem and how can we ensure that when the machine (either physical or virtual) reboots, all the Linux VM's startup properly.

Thank you very much.