Luckily the Error Log did have more details, but first you had to display it. To see the Error Log, go to the Window menu, then Show View, then Error Log.
From there I could see that the actual error was "Could not obtain an OAuth2 access token." That was finally getting me somewhere.
Basically what that is saying is there is something wrong with the authorisation of your account during deployment. In my case, I've not done a deploy for several months so it's likely that my access token simply expired. Resolving that is simple, as Roy would have put it "Have you tried turning it off and on again?" Yep, all you need to do is log out of your Google account in Eclipse and then log back in. To log out, click your Google account in the bottom right part of the Eclipse window.
Deployment worked without any issues after signing back in.