In the version of Eclipse I’m using (Indigo service release 1), the “Rename” option doesn’t come up for the default package (unlike other packages) – but if you select all the classes then right-click and select “Move” that will let you put them in a new package.
(As far as I can tell, the Rename option is for renaming classes without changing their package, but Move certainly works for moving between packages.)
Screenshots of the process:
Original situation
Select all classes and show the Refactor part of the context menu
Select “Move”, click on Create Package and type in a name (mypackage in this case)
The final result
Alternatively, if you want to move them to an existing package, you could just drag and drop the classes.
For those suggesting Refactor -> Rename on the package, here’s a screenshot showing that not working on my machine:
