MySQL version won't update

I’m trying to update my WP site from 3.1.3 to the latest version, but the update page says “You cannot update because WordPress 3.3.2 requires MySQL version 5.0 or higher. You are running version 4.1.11.”
I just contacted my host (Gate.com) and they migrated my site to a MySQL 5 database server. When I login to my database to confirm, it says it’s running version 5.1.52.
What to do?