Rebuild the base box. First, bring it up without provisioning and SSH to it.
vagrant up --no-provision
vagrant ssh
Then, perform the commands you need to update the box. This can include updating Chef and Ruby. Optionally, update the packages for the OS, etc. You should clean up the box of everything that isn't required, such as downloaded package files or caches.
For example, I use the Opscode Omnibus Full Stack Installer for Chef in my Vagrant boxes (originally built with VeeWee), and I update the packages, too.
sudo dpkg --purge chef chef-full
sudo true && curl -L https:
sudo apt-get update && sudo aptitude safe-upgrade
sudo rm /var/cache/apt/archives
Don't forget to "zero" the disk to reduce the size.
sudo dd if=/dev/zero of=/EMPTY bs=1M
sudo rm /EMPTY
exit
Then, package the box up and add it to your Vagrant environment for use.
vagrant package
vagrant box add mynewlucid32 package.box
If you want to use the same box name, you'll need to remove the existing box (~/.vagrant.d/boxes/BOXNAME) first.