Authentication failure during Vagrant Up, while vagrant ssh and ssh vagrant@localhost -p2222 works

I would like to execute a shell script using Vagrant at boot. Vagrant is unable to Authenticate, while the VM has been started using vagrant up:

c:\temp\helloworld>vagrant up
Bringing machine 'default' up with 'virtualbox' provider...
==> default: Importing base box 'helloworld'...
==> default: Matching MAC address for NAT networking...
==> default: Setting the name of the VM: helloworld_default_1398419922203_60603
==> default: Clearing any previously set network interfaces...
==> default: Preparing network interfaces based on configuration...
    default: Adapter 1: nat
==> default: Forwarding ports...
    default: 22 => 2222 (adapter 1)
==> default: Booting VM...
==> default: Waiting for machine to boot. This may take a few minutes...
    default: SSH address: 127.0.0.1:2222
    default: SSH username: vagrant
    default: SSH auth method: private key
    default: Error: Connection timeout. Retrying...
    default: Error: Authentication failure. Retrying...
    default: Error: Authentication failure. Retrying...
    default: Error: Authentication failure. Retrying...
    default: Error: Authentication failure. Retrying...
    ...

After executing CTRL + C it is possible to authenticate to the VM using vagrant ssh and ssh vagrant@localhost -p2222

Vagrant file

I use the default Vagrantfile and I only changed the hostname:

# -*- mode: ruby -*-
# vi: set ft=ruby :

# Vagrantfile API/syntax version. Don't touch unless you know what you're doing!
VAGRANTFILE_API_VERSION = "2"

Vagrant.configure(VAGRANTFILE_API_VERSION) do |config|
  # All Vagrant configuration is done here. The most common configuration
  # options are documented and commented below. For a complete reference,
  # please see the online documentation at vagrantup.com.

  # Every Vagrant virtual environment requires a box to build off of.
  config.vm.box = "helloworld"
  ...

Vagrant version

c:\temp\helloworld>vagrant --version
Vagrant 1.5.1

Question

How to authenticate to VM using vagrant up?