Ssh – Vagrant not ready for SSH error on VirtualBox and Laravel Homestead

Vagrant Version: 1.6.3
VirtualBox: 4.3.14
Ubuntu 14.04 LTS 64 Bit

I have been on this for a pretty good while now and cannot figure this out. I have my public and private keys setup and they work. I know they are not the problem at they worked fine before I updated Ubuntu from 32 Bit to 64 Bit. I have uninstalled and reinstalled all software mentioned and still no fix. This is on a Laravel Homestead instance but it is happening on all my boxes, including the precise32 from vagrants home page.

When I run vagrant ssh-config The error I am getting is

    The provider for this Vagrant-managed machine is reporting that it
    is not yet ready for SSH. Depending on your provider this can carry
    different meanings. Make sure your machine is created and running and
    try again. Additionally, check the output of `vagrant status` to verify
    that the machine is in the state that you expect. If you continue to
    get this error message, please view the documentation for the provider
    you're using.

This did not happend when I was on 32 Bit, but I had other issues when is what caused me to move up to 64 Bit.

When I run vagrant up, it stops on this line:

==> default: Running 'pre-boot' VM customizations...
==> default: Booting VM...
==> default: Waiting for machine to boot. This may take a few minutes...
default: SSH address: 127.0.0.1:2201
default: SSH username: vagrant
default: SSH auth method: private key

Any thoughts on this would be welcomed. I hate that this is happening as I just recently released a podcast episode on how awesome development on Vagrant WAS as of right now, its sucking my time to try to get this in order. Thanks to all in advance!