Hello,
I have worked it out my self with the help of sparkx at virtuemart.net. Here you can find his post and my post with the answer that is the same below but I link it here in case it develops with more replies.
What I had to do, is to simply change the main menu Shop from English language to All as VirtueMart seems to look for the All language when you translate the categories.
sparkx talks about creating a new All language menu and later unpublising it. But that did not work for me. Instead, it was working before unpublishing but then English and ALL menus appeared duplicated.
I think, this is a bug from Virtuemart. I am using Joomfish 2.5.1 and it created the menus in the first place just having English and Spanish in my menu list. It would be awesome if someone of the developers can change VirtueMart to take the reference menu as the default (in my case English) and not the language All.
Hope this help in the future.
Borja