I think the point is the comparison. You need to compare new lents with existing lents other then compare them with the lent in Trigger.oldMap.

I made two changes to your code:

1. added the code to get the books and their existing lents.

2. updated the comparison.

trigger UpdateCount on Lent__c (before insert,after insert,after delete) 
{
	List<Contact> counts_toUpdate = new List<Contact>();
	Map<String, Integer> contact_newCount_Map=new Map<String, Integer>(); //for each contact the CountNumber
	// Start, gets books and their lents.
	Set<Id> bookIds = new Set<Id>();
	for(Lent__c lent : Trigger.new)
	{
		bookIds.add(lent.Book__c);
	}
	Map<Id, Book__c> books = new Map<Id, Book__c>([select Id, (select Id from Lents__r) from Book__c where Id in :bookIds]);
	// End
	if(Trigger.isInsert)
	{
		List<Lent__c> counts =[select Book__c,Contact__c, Contact__r.Count__c,Book__r.Name
								from Lent__c where id IN :Trigger.new FOR UPDATE];
		for(Lent__c lent:counts)
		{
			// Updated the comparison.	
			if(lent.Book__c!= null && books.get(lent.Book__c) != null && books.get(lent.Book__c).Lents__r != null && books.get(lent.Book__c).Lents__r.size() > 0)
			//if((lent.Book__c!= null) && (lent.Book__c != Trigger.oldMap.get(lent.id).Book__c))
			{
				lent.Book__c.addError('Another new lead has the same email address.');
			}
			else
			{
				contact_newCount_Map.put(lent.Contact__c, Integer.valueOf(lent.Contact__r.Count__c==null ? 0 : lent.Contact__r.Count__c) + 1);
			}
		}
	}
	else if(trigger.isdelete)
	{
		Set<Id> contactIds = new Set<Id>();
		for (Lent__c l : Trigger.old)
		{
			contactIds.add(l.Contact__c);
		}
		//List<Lent__c> counts = [select Contact__c, Contact__r.Count__c
		//from Lent__c where id IN :contactIds];
		Map<Id,Contact> oldContacts = new Map<Id,Contact>([SELECT Count__c From Contact where Id IN :contactIds]);
		for(Lent__c lent : Trigger.old)
		{	
			contact_newCount_map.put(lent.Contact__c, Integer.valueOf(oldContacts.get(lent.Contact__c).Count__c == null ? 0 : oldContacts.get(lent.Contact__c).Count__c ) -1);
		}
	}
	for(Contact con : [select id, Count__c from Contact WHERE ID IN : contact_newCount_Map.KeySet()])
	{
		con.Count__c=contact_newCount_Map.get(con.id);
		counts_toUpdate.add(con);
	}
	update counts_toUpdate;
}