Hi.
At first please describe what you've done. Because when you'll delete a contact of the user (Administrator -> Manage users, or CRM -> Contacts), then actually user is not deleted. You can still log in, however you'll not access a lot of things. To deactivate user you need to go into Administrator -> Manage users and click little green dot in the record actions. Actually there is no way to physically delete user entry from the database if you've got Contacts module installed, so I think that you should still have this user in the database.
If you've just deleted a record contact then go to the Administrator -> RecordBrowser -> select [ contacts ] -> activate deleted contact with little gray dot.
If you've done something else then open your database (phpmyadmin, console or other tools), go to the user_login table. Check if there is a user. Activate it, if it's not. Reactivate a contact for this user also.
Regards,
Adam