Full reinstall --- sounds like windows to me
It's very rare problems which would require a full reinstall of Ubuntu. You should be able to remove vmware, even if it requires a bit of 'manual labour' in the console to do it.
First of all, if you still have the original install directory from the old version of vmware, then there's an uninstall script within it which might help. I had mine in the following place:
Where you put it on your machine will vary, but you can run this file to uninstall the old version if you still have the install directory around.
Otherwise I'd try something like the following:
sudo apt-get autoclean # automatically remove old downloaded packages
sudo updatedb # This will take a while
locate vmware > /tmp/vmware.list # find all occurences of vmware in filenames
Then look through the list and try to work out what can be removed. Probably most of it, but you'll want to look at some of the files, and make sure not to delete your virtual machines (*.vmx, usually).