I had an issue with this with an existing box (not sure what changed), but I could connect via SSH, even though the Vagrant box failed to boot up. As it happens my SSH key had changed somehow.
From the vagrant root folder I ran vagrant ssh-config
which told me where the key file was. I opened this with puttygen and then it gave me a new key.
On my Linux guest, I edited ~/.ssh/authorized_keys
and dropped the new public key in there.
Everything is working again - for now!