Thanks to Jeremy Cioara from Cisco Blog for directing our attention to this article on Cisco’s site:
http://www.cisco.com/en/US/products/hw/switches/ps5213/products_tech_note09186a0080a49dbf.shtml

However, one interesting thing I noticed in the article was the absence of a differentiation between how the VLAN.dat file can be deleted on a Catalyst 6500 series switch and how it is deleted on a 4500 series switch. In my experience the two are not the same.

I have tried to use the delete command on a 4500 series switch without success. The command executes and a access denied error is returned (if my memory serves). The only way to delete the VLAN.dat file on this platform is to erase the cat4000_flash volume. This will clear the file.

So, the full command is:
erase cat4000_flash:

One thing to note is that the erase command was tested on the pre-E-Series 4500 platform. I have not tested it on the E-Series hardware.