You've probably worked this out by now but anyway it may be helpful for someone - I've just been having a play around with the built in WP gallery function and to address your initial question, I don't think it's necessary to 'upload' your pictures again so (you have multiple copies of the same pic) to create a new gallery.
The other way (though it's a little unintuitive and I think where improvement could be made without imposing constraints or affecting the flexibility of WordPress) is to add the existing photos you want to be in your 'gallery' to the new post from the media library as per usual. You'll then find the gallery tab appears in the media uploader. Click on this and choose your gallery options and insert.
Then you'll have to delete the code for the photos you have inserted but leaving the gallery shortcode there.
In order to add extra images to this gallery you'll need to add them to the post, then delete the code again - leaving the original gallery shortcode in place. You will find your new photos are now in the gallery.
This does seem a little bizarre to me. I can't really see how including a facility within the gallery tab to add images directly from the media library to a gallery could have any negative effect.
It may be one of those things that is not on the list of priorities for WP development or there may well be other considerations.
I've used NextGen on a number of sites and it's a great plugin, however, for many people it adds layers of complexity and management when all they want is a simple way to add a basic gallery.
The built in WP gallery functionality is so close to doing that it would be great to see some small improvements made.
Notwithstanding the above, full credit to WP dev team and all plugin developers everywhere for making WordPress awesome.