@xisco yes, xenstore-utils was installed - i suppose it was installed by ubuntu setup

For anyone who might stumble upon this issue (since is one of ~ 5 results when googling it)
Had the same Error in Ubuntu 17.04 and

 sudo apt-get remove xenstore-utils

solved my problem