so you still have the old device...
does it still power up?
If it does you could use pimbackup to create a backup file of all your contacts. Just install on old device make the backup file. Save it to sd card. Install it on new device. Then restore from the file on the sd card..
Its a good program to have anyway. I have mine set up to make a backup 3 times a week deleting the old backup file each time. Works excellent.
Get it here.
http://pocketpcfreewares.com/en/index.php?soft=1806
Also on why it deleted your contacts. You must have it syncing whatever is on the server. Meaning that there must have not been any contacts on the server. Then instead of it copying all contacts from phone to server it copied from the server to the phone. There is a setting somewhere on that in active sync.