What process did you follow (or, what steps did you take) to reach the point where you encountered these errors?

I'm having no luck at all with Vagrant 1.3.1.
Installed Vagrant using the installer. Appears to work OK for VirtualBox.
But the external compiler code appears to be broken so I get:

mbell@dogbert /cygdrive/c/temp/vagrant
$ vagrant plugin install vagrant-digitalocean
Installing the 'vagrant-digitalocean' plugin. This can take a few minutes...
C:/Tools2/Vagrant/embedded/lib/ruby/site_ruby/1.9.1/rubygems/installer.rb:556:in `rescue in block in build_extensions': ERROR: Failed to build gem native extension. (Gem::Installer::ExtensionBuildError)

C:/Tools2/Vagrant/embedded/bin/ruby.exe extconf.rb
creating Makefile

make
generating generator-i386-mingw32.def
compiling generator.c
linking shared-object json/ext/generator.so

make install
/usr/bin/install -c -m 0755 generator.so C:
/usr/bin/install -c -m 0755 generator.so .
/usr/bin/install: `generator.so' and `./generator.so' are the same file
make: *** [and] Error 1

Unfortunately I'm sufficiently new to this area to not be sure whether this is an error in the vagrant-digitalocean plugin or the as-provided Vagrant 1.3.1 windows installer.

and having spent several hours trying to find a work-around, I'm preparing to give up on the idea of using Vagrant to provision a test machine on DigitalOcean. Anybody got any suggestions?

Try installing the ruby-dev package -- does that fix it?

I was having similar problems and fixed it by installing the older 1.2.7 version of Vagrant