Migrate GitLab to another server


I inherited Ubuntu 14 server with gitlab-ce omnibus package version 8.6.1. I am trying to migrate to a new Ubuntu 16 server and then update gitlab to newest version.
But it seems that the current installation (on Ubuntu 14) is not OK. When I run gitlab-rake gitlab:check I get a failure at All migrations up?. More detailed info from gitlab-rake db:migrate:status shows that a lot of IDs are down. If I try gitlab-rake db:migrate it fails at the first ID that is down.
What else can I try to fix the installation before attempting to migrate?
I have tested the migrate procedure (backup, restore) to another server and later update gitlab to newest version but the update fails with the same error.