1.) Open the Database Deployment Toolkit2.) Open the appropriate profile3.) Click on "Object Name History" in the tree view4.) To clear all items, right-click in the detail (right) panel5.) Click "Clear History"6.) This will remove all history records.7.) Rebuild the package8.) 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.
Thanks