Isso é meio ruim na minha opinião para ser uma solução real para o problema, mas finalmente descobri como fazer login na minha conta com acesso root. Eu estou hospedando com o GoDaddy e quando você configura seu servidor virtual privado com eles, você é solicitado a criar um usuário para o seu servidor, o que eu fiz. O que eu não percebi ao executar este passo é que o nome de usuário que eu selecionei também seria o nome de usuário que eu precisava usar no ssh para acesso root. Eu estava tentando fazer o login com root
como o nome de usuário e falha. Quando finalmente tentei fazer login com o nome de usuário que a GoDaddy me pediu quando criei meu VPS, consegui fazer o login com acesso root. Eu decidi postar a minha resposta no caso de alguém se deparar com este problema. Eu também adicionei "GoDaddy" à minha pergunta, percebendo que esse problema poderia ser isolado da forma como eles configuraram você com um VPS (e não suportam btw).
Muito obrigado a @ulovah por toda sua ajuda. Você me ajudou a descartar muitas possibilidades.