This error just started on a trigger that has been running perfectly for many months.

PaymentDuplicatePreventer: execution of BeforeInsert caused by: System.QueryException: Non-selective query against large object type (more than 100000 rows). Consider an indexed filter or contact salesforce.com about custom indexing. Even if a field is indexed a filter might still not be selective when: 1. The filter value includes null (for instance binding with a list that contains null) 2. Data skew exists whereby the number of matching rows is very large (for instance, filtering for a particular foreign key value that occurs many times) Trigger.PaymentDuplicatePreventer: line 23, column 2

All this trigger is supposed to do is stop duplicates based on the unique code, which is just a formula field that combines two other fields on the record. Here is the trigger. It is pretty much copied exactly from the force.com cookbook about how to prevent duplicates. Any help is appreciated, thanks.

trigger PaymentDuplicatePreventer on Payments__c(before insert)
{
	//Create a map to hold all the payments we have to query against
	Map<String, Payments__c> payMap = new Map<String, Payments__c>();
	
	//Loop over all passed in payments
	for (Payments__c payment : System.Trigger.new)
	{
	
		// As long as this payment has a payment code and either it's an insert or it's doesn't conflict with another payment in this batch */
		if ((payment.UniquePaymentCode__c != null) && (System.Trigger.isInsert || (payment.UniquePaymentCode__c != System.Trigger.oldMap.get(payment.Id).UniquePaymentCode__c)))
		{
		
			// Make sure another new payment isn't also a duplicate. If it is, flag it, if not, add it
			if (payMap.containsKey(payment.UniquePaymentCode__c))
			{
				payment.UniquePaymentCode__c.addError('Another new payment has the same unique identifier.');
			}
			
			else
			{
				payMap.put(payment.UniquePaymentCode__c, payment);
			}
		}
	}
	
	/* Using a single database query, find all the payments in
	the database that have the same uniquepaymentcode as any
	of the payments being inserted or updated. */
	if(payMap.size() > 0)
	{
		for (Payments__c payment : [SELECT Id,UniquePaymentCode__c FROM Payments__c WHERE UniquePaymentCode__c IN :payMap.KeySet()])
		{
			try
			{
				Payments__c newPay = payMap.get(payment.UniquePaymentCode__c);
				if(newPay != null)
				{
					newPay.UniquePaymentCode__c.addError('A payment for this person in this study already exists.');
				}
			}
			catch ( System.DmlException e)
			{
				payment.adderror('Payment' + payment.UniquePaymentCode__c + 'Error ' + e);
			}
		}	
	}
}