Hello Chouby and Alessio.
I believe I found a possible solution for this conflict.
The short answer:
small change on line 243 in /polylang/include/core.php (Polylang 0.9.4)
//added "empty($_GET['callback'])" check to avoid conflict with NextGen Gallery
if ( empty($_GET['callback']) && str_replace('www.', '', home_url('/')) == trailingslashit((is_ssl() ? 'https://' : 'http://').str_replace('www.', '', $_SERVER['HTTP_HOST']).str_replace(array('index.php', '?'.$_SERVER['QUERY_STRING']), array('', ''), $_SERVER['REQUEST_URI'])))
The long answer:
NextGen Gallery (NGG) makes calls to /index.php?callback=xxx (and some other args).
This calls are caught by the above redirect and NGG plugin never gets to see it.
This does not only affects adding a gallery to a post, but also setting a featured image coming from a NGG uploaded picture, and probably some more conflicts.
I would prefer not to modify /polylang/include/core.php, but maybe Chouby can come up with a better solution.
WP Multisite 3.4.2 + Polylang 0.9.4 + Nextgen Gallery 1.9.6
Chouby, it seems we are using different NGG versions
Best regards :)