I successfully installed a freshly downloaded virtual instance a few days ago, running in VirtualBox on Windows 10. Seems to be working fine. Noticed that under 'Statistics' on the home page is was dated April 2016. Configured with a key for replication, ran 'bin/replicate start' and now the Statistics page update is 05/22/16. Interestingly the mirror http://musicbrainz-mirror.eu:5000/ shows the same 05/22/16 date.
It seems the database schema changed on 05/23/16 (https://blog.musicbrainz.org/2016/05/25/schema-change-release-2016-05-23-with-upgrade-instructions/) but the virtual machine available for download is dated 2015-08-06 on http://musicbrainz.org/doc/MusicBrainz_Server/Setup
So automatic updating stops at 5/22 with the current virtual machine. Seems to make sense but where is the latest virtual machine build, or is that left to the user to build from the GitHub repository?
Follow the instructions to update the schema:
https://blog.musicbrainz.org/2016/05/25/schema-change-release-2016-05-23-with-upgrade-instructions/
Note that you may need to update PostgreSQL to 9.5 (the VM image has an older version) first. Also, since more than a month has passed from your version, it may be easier to import a new dump and then turn the replication on, rather than go through all incremental updates.
EDIT:
You can find the latest VM here.