Yes, it is 3.0.1 from Feb 2012 (as shown on one of the screen shots I sent you)

I do not use any cache at this point.

I have disabled this SEF URL :
SEF URL : gotocategory
NON SEF : index.php?option=com_hwdvideoshare&task=gotocategory&Itemid=498

And now, all the category menus give a 404 error, so this seems to be the problem. How can I delete this entry ? I can't find that option in the 'Manage SEF URL' menu

I found the delete option. Whenever I delete this SEF URL, it comes back as soon as I click on a menu category again. But it works once (before the item comes back)

there are 4 columns in the SEF URL manager :
Enabled, SEF, Locked, active

If in the second column, when I choose non SEF, the categories from the menu start to work again fine. So this seems to solve the problem. I am curious as to what the problem really was though...

Any idea what could be causing the categories not to be appended in the viwvideo part ?

I'm sorry, I don't have any idea what could cause such problem. Try deleting some video URL in JoomSEF's URLs manager to see if it will be recreated without the category again.
As we were unable to reproduce the problem, I can only offer you our paid support service to check the problem directly on your web server: www.artio.net/e-shop/support-services/joomla-related-support-1h

I found the problem : I had selected the 'Allow multiple categories' option and apparently the SEF plugin does not like that ... Problem solved. Thanks for your help.