Thanks to my friend Gary, under the threat of switching to Fedora
the issue is now solved. And I believe I now understand what I have done.
I initially installed VB 2.1 and saw that it created a launch command VirtualBox... I though, there must be virtualbox either, being a linux system... I ran it and did not tell me the command was not available... it told me "The program 'virtualbox' is currently not installed. You can install it by typing:
sudo apt-get install virtualbox-ose
Ok, I am dumb, but I thought that was just a starting script (end in ose, which is not the name of the product...). Instead installed the whole package, most probably corrupting the installation.
We reinstalled everything from scratch and now it works...