I just tested the plugin with a newly installed WP 2.7.1 DE-Edition (Content was migrated from an old blog).
I tried IE, Chrome and FF all current Version.
I was not able to create a navigation category inside the backend. Therefore I wasnt able to test anything else except the unistall -- which didnt work as well.
Conclusion: I dont know how this plugin good so much good ratings, is clearly broken.