Photoshop, Premiere, and After Effects are the programs I use for making DVD menus. You will find that After Effects has better quality transitions than Premiere, and the more technical things you want to do with your video can be done easier and more efficient with it. Master all three programs and you will have a very powerful package in your arsenal.
I have not yet compared sega's SC ROTJ to my US discs, but I should be doing some caps on my player tonight and have something to show you tomarrow.
Also, look for our newest article to be up within the next hour.