When using WP No Category Base, it removes more then just the category base, it also removes anything else between the domain name and the actual category name. This is a problem with multilingual website, when any other language then the default language adds /lang/ behind the domain name.
For qTranslate, there's already a fix found. Does anyone now a hack to work with WPML?
The qTranslate hack is here: http://wordpress.org/support/topic/resolved-plugin-wp-no-category-base-compatibility-with-qtranslate-plugin