Are you using Premiere 6.5? This is rather limited in the creation of DVD in that it can "only" make DVD compliant MPEG2 files - those that would be recognised by a DVD player. You'll need a seperate application to actually author and create the necessary VOB files and file structure to make a playable DVD. I know of a freeware app (ifoedit) that will create all the files you need leaving you to burn the folders and files to DVD using a burning app.
What it doesn't do is create the funky menus you want. To do this you'll need a DVD authoring app such as Ulead DVD MovieFactory 2 or Sonic MyDVD. These are relatively inexpensive and extremely user-friendly. unfortunately I don't know of any freeware alternatives, but I do know that most of the authoring apps come with trial periods - so try before spending those precious £/$s!
I've written a few guides to DVD creation at my site if you want to check those out, or you can search the forums for any info on DVD creation. To be honest, creating menus is childs play - and is essentially as you describe in that you import the images you want. Its then just a matter of adding text/thumbnails and linking those to your movie(s). You can make a polished DVD as good as all but the more extravagent Hollywood productions
dvd menu 
Linear Mode
