I have a bi-lingual blog, English and Chinese, with the language settings handled by WPML.
In the sidebar, I use the default WordPress categories widget to list the blog categories. WPML automatically displays only the relevant language categories; so on the English pages it lists the English language category names, and on the Chinese, it lists the Chinese language names.
When I activate the WordPress SEO, the category lists get switched! The English blog pages display a list of the Chinese categories, and vice versa. Disabling the SEO plugin puts things right straightaway.
Any idea where the conflict might be? I am happy to describe specific settings in either plugin to help bug-fix.