We've noticed that when using All in one SEO Pack together with WPML there is a (critical) bug with the Canonical URL.
site.com => ok
site.com/fr => gives site.com as canonical, resulting in not-indexing the main page(s) of the other language(s).
I've fixed this by replacing (aioseop.class around line 520 in the is_home() conditional):
$link = get_option('home');
$link = home_url( '/' );
There are more issues, i.e. with paged category pages.