The only officially supported version of VMware Fusion under OS X 10.9 Mavericks is VMware Fusion 6. Some Users have reported VMware Fusion 4.x works for them while others reported many issues and upgraded to VMware Fusion 6.
So, make proper* backups of your VM's and give it a try and or download the latest version of VMware Fusion 6 (6.0.3 at the present time) and take it for a free 30 day trial.
==========
* It is a known fact that Time Machine is not 100% reliable backing up/restoring Virtual Machines under all circumstances/conditions. Also backing up Virtual Machines via Time Machine is disk/time intensive and wastes a tremendous amount of space for something that may be corrupt and worthless come time to restore it. At a minimum I would exclude Virtual Machines from Time Machine and with the Virtual Machines shutdown, not suspended, and VMware Fusion closed then manually copy the Virtual Machines Package(s) to an alternate location, preferably on to a different physical hard disk. Then keep the User Data that is stored within the Virtual Machine backed up off of the Virtual Machine on a regular basis so as to always have a current User Data Backup. If you have to restore a properly backed up Virtual Machine that is not as current at least you'll have a working Virtual Machine and current User Data to go forward with when you find out your Time Machine Backup of the Virtual Machine fails.
Also have a look at: Best Practices for virtual machine backup (programs and data) in VMware Fusion (1013628)
