Made it work with Ubuntu 14.10

install_vagrant_sudoers.sh

#!/bin/bash
# Add Vagrant's hostupdater commands to sudoers, for `vagrant up` without a password

# force sudo on self.
if [ $( id -u ) -ne 0 ]; then
    exec sudo -p "Login password for %p: " "$0" "$@"
    exit $?
fi

# Stage updated sudoers in a temporary file for syntax checking
TMP="$(mktemp)"
cat /etc/sudoers > "${TMP}"

# Remove any previous declarations
sed -i -e '/Cmnd_Alias VAGRANT_*/ d' "${TMP}"

sed -i -e '/# Allow passwordless startup of Vagrant when using NFS\./ d' $TMP
sed -i -e '/# based on https:\/\/gist.github.com\/joemaller\/6764700/ d' $TMP

sed -i -e '/NOPASSWD: VAGRANT_*/ d' "${TMP}"

cat >> "${TMP}" <<EOF

# Allow passwordless startup of Vagrant when using NFS and vagrant-hostsupdater plugin
Cmnd_Alias VAGRANT_EXPORTS_ADD = /usr/bin/tee -a /etc/exports
Cmnd_Alias VAGRANT_EXPORTS_REMOVE = /bin/sed -E -e /*/ d -ibak /etc/exports
Cmnd_Alias VAGRANT_HOSTSUPDATER_ADD = /bin/sh -c echo "*" >> /etc/hosts
Cmnd_Alias VAGRANT_HOSTSUPDATER_REMOVE = /bin/sed -i -e /*/ d /etc/hosts
%admin ALL=(root) NOPASSWD: VAGRANT_EXPORTS_ADD, VAGRANT_EXPORTS_REMOVE, VAGRANT_HOSTSUPDATER_ADD, VAGRANT_HOSTSUPDATER_REMOVE
EOF

# Check syntax and overwrite sudoers if clean
visudo -c -f $TMP
if [ $? -eq 0 ]; then
  echo "SUCCESS: Adding vagrant commands to sudoers"
  cat $TMP > /etc/sudoers
else
  echo "sudoers syntax wasn't valid. Aborting!"
fi

rm -f $TMP

This script works on Ubuntu 14.10. However the actual sudoers settings do not work. My guess is that the wildcards are not taken into account. Alternatively change the script to "allow" the programs without parameters such as "Cmnd_Alias VAGRANT_HOSTSUPDATER_REMOVE = /bin/sed". However this has negative security implications.

Wish I had seen this much sooner.
If you were still having trouble with it on Ubuntu you might jump into the conversation here agiledivider/vagrant-hostsupdater#50 (comment)

Also I updated the script with better cleanup and the latest sudo commands being used.