Hi,
I get the exact same error and cannot find any solution to it.
I tried installing VM 3.0.16 on Joomla 3.5.1 (PHP 5.6) with the Joomla installer and get the same messages "vmError: Could not find VirtueMart submenues" and Update Server not found. I am pretty sure that I uninstalled VM once, so it is not a fresh installation (but I installed and re-installed so many times now that I am not 100% sure any more

).
I had VM running on this host/Joomla version before but had to re-set up the site completely after it has been hacked. So it is rather no provider problem.
I tried with older VM versions, with version 3.0.17, set the PHP version down, checked the folder/file permissions with Akeeba Admin Tools, but nothing helped..
There must be more information to this error.. Please if anyone has any tips, I'd be glad to hear.
I would try installing manually, but I don't really know how. Can someone tell me how to manually install VM or post a tutorial? Simply uploading the folders is not everything, I guess...
It would be really great to get some hints on how to solve this problem because it makes using VM impossible..
Thanks!
Michael