Do you have a history in your profile? If you have renamed your database at any point, a history record will get created for valid name changes. However, sometimes when you are initially creating your data, you may rename several times. When this happens you need to remove the database history rename records. To remove your history records do the following:1.) Open the Database Deployment Toolkit
2.) Open the appropriate profile
3.) Click on "Object Name History" in the tree view
4.) To clear all items, right-click in the detail (right) panel
5.) Click "Clear History"
6.) This will remove all history records.
7.) Rebuild the package
8.) Attempt to deploy to your database again.
If this doesn't resolve your problem let me know. But it sounds like there is some history doing some clean up. I imagine that you created a database and then deleting it at some point, so the history is smoking the database since there is an object history.