You should be doing a re-direct. Atleast the bots will know the pages have moved and will be able to find them.
Shouldn't be any harm keeping those old pages for a little while, until the new ones are indexed.
Big question, though.
Are you on a unix server or windows iis ?
If it's unix, then it's as simple as uploading an .htaccess file and entering something like:
Redirect /old/oldfile.html
http://yoursite.com/new/newfile.html
All on 1 line
On Windows, then you're looking at using a third party tool, such as:
ISAPIRewrite
www.isapirewrite.com
IISRewrite
www.qwerksoft.com/products/iisrewrite
I'll pass on the UFO, thanks LOL !