This can be done quite easily, but must be done after the old server is demoted and fully removed from the network.
The first step is to create a DNS alias (CNAME) record. Name it the name of the old server and place it in your Active Directory domain's Forward Lookup Zone. Specify the full name of the new server (newserver.ad.domain.com) as the address to map to.
The second step is to configure the name of the old server as an additional NetBIOS name on the new server. This requires a registry change and is described in more detail at
http://thelazyadmin.com/blogs/thelazyadmin/archive/2006/07/18/Configuring-Additional-NetBIOS-Names.aspx.
In doing this, the new server will still be accessible using either its new name or its old name, although remember that the shares on the server must have exactly the same name for the shortcuts to not be broken.
-Matt