When connect is used the devices try to establish a connection but revert to the “saved, secured with WPA/WPA2”. After it has attempted to do this a few times the message changes to “Authentication Problem”.
That suggests you (or the router) have the wrong password or the wrong protocol; it has saved the password, and says the link is encrypted with WPA/WPA2. The fact that you are getting ‘Authentication Problem’ points to a problem with, well, authentication…
The fact that removing the MyCloud from the router makes no difference points to it not being an ongoing problem caused by the MyCloud.
I’d have a careful look at the router settings. Are you sure that no access time windows are set, or any other strange settings? A factory restore of the router might be in order, but make a careful note of your network access ID and password (your Virgin Media account details, that is). Or just contact Virgin customer support. And wait…
I don’t have a Virgin router, but mine has a ‘network view’, which shows what devices are connected to it (or have been), and what their IP address is, and the protocol used to establish an IP address. Find a similar page on your router, and check the IP addresses for the devices, and check what IP addresses your devices think they are using (Settings/Wifi/(three dot menu)/Advanced). You can usually get the router to ‘forget’ them all, and restart connections (after setting the connection protocol to DHCP). There’s usually an ‘allow all devices to connect automatically’ setting, or something similar.
I suspect the problem may be coincidental to getting your MyCloud, but it’s just possible that the MyCloud has used some router UPnP commands to try to establish a route out of your network (for cloud access), and this has messed up the router.
The other question then arises: which method did you use to set up your MyCloud? The online setup, or just the Dashboard? How are you accessing the MyCloud; WD Desktop and WD QuickView, or just mapped into your file system?