Hi! I just wanted to thank you and add that it does work with SEO activated for me and that a menu item's child in a second language has to be assigned to the proper parent menu item of that language in order to be seen(in the Menu Item Details).
Some people may say "these things are easy to see" but I liked the extension and if someone that is considering to use it, read some of the comments below may get discouraged. I use joomla! 1.5.10 with greek language pack and M17n v1.5.2, I am a noob and I had no problem.