My database is out of date?

I recently switched web hosting providers and tried to install the latest version of wordpress. For some reason I have been having non stop errors and have not been able to successfully install it. I have deleted all the files and uploaded them several times, but to no avail. I have installed wordpress many times before and have never had any of these issuses before. The latest one is this error “Your database is out-of-date. Please upgrade.” My database is empty, so I don’t know why it would say this. When I go to the upgrade.php file, it gives me the same message. Any ideas?