Ok, this is weird.  I have a trigger that has been working happily for a few months now.  Today, I went to add some functionality to it in Sandbox, and am getting a 'List index out of bounds' error where (a) it previously worked in Sandbox, and (b) it currently works in Production.  I get this error when trying to create a new Lead.

I threw a bunch of system.debug statements around it to try and identify the problem, and blast it, I can see what line it goes wrong on, but don't know why!  Basically, I am getting a Lead ID from trigger.new and using it in a SOQL statement to retrieve the relevant fields.  This is an 'after insert' trigger where I am updating some fields.  I am successfully retrieving the list of Lead ID's from the trigger.new 'for' loop.  When I check for the size of this list outside of the for loop, it says it has a size of 1, which is correct.  I can show that ID in the debug log.

But then, when I make my SOQL query using this ID list, I get a return set of 0 size!

This makes no sense.  It has been working fine, and I can see that the list I get from trigger.new is NOT zero.  But for some reason the SOQL query doesn't return anything.

Here are the relevant codes of line and results:
-----------------------------------------------
ERROR RECEIVED:
Error: Invalid Data.
...execution of AfterInsert caused by: System.ListException: List index out of bounds: 0... (Points to the last line of code given below)

RELEVANT CODE:

List<Lead> submittedLeadList = new List<Lead>();
List<Id> theLeadID = new List<Id>();

system.debug('Entering the FOR loop to read trigger.new Lead');

for (Lead leadList : trigger.new) 
     {
        theLeadID.add(leadList.Id); 

        system.debug('Lead ID:  ' + leadList.Id);
        system.debug('Lead Name:  ' + leadList.FirstName + ' ' + leadList.LastName);
     }

system.debug('Exiting FOR loop');
system.debug('Lead ID after exiting loop:  ' + theLeadID[0]);
system.debug('Number of Leads retrieved from trigger.new:  ' + theLeadID.size());

submittedLeadList = [SELECT Id, FirstName, LastName, Company, Requested_Quote_Types__c, State, New_Lead__c FROM Lead WHERE Id IN : theLeadID LIMIT 1];

system.debug('Lead List Size:  ' + submittedLeadList.size());

system.debug('SOQL Query for submittedLeadList, for Lead:  ' + submittedLeadList[0].FirstName + ' ' + submittedLeadList[0].LastName);

DEBUG RESULTS:
USER_DEBUG|[32]|DEBUG|Entering the FOR loop to read trigger.new Lead
USER_DEBUG|[38]|DEBUG|Lead ID:  00Q63000003cPewEAE
USER_DEBUG|[39]|DEBUG|Lead Name:  Test Test1
USER_DEBUG|[42]|DEBUG|Exiting FOR loop
USER_DEBUG|[43]|DEBUG|Lead ID after exiting loop:  00Q63000003cPewEAE
USER_DEBUG|[44]|DEBUG|Number of Leads retrieved from trigger.new:  1
SOQL_EXECUTE_BEGIN|[46]|Aggregations:0|SELECT Id, FirstName, LastName, Company, Requested_Quote_Types__c, State, New_Lead__c FROM Lead WHERE Id IN :tmpVar1 LIMIT 1
SOQL_EXECUTE_END|[46]|Rows:0
USER_DEBUG|[47]|DEBUG|Lead List Size:  0
FATAL_ERROR|System.ListException: List index out of bounds: 0

This is an "after insert" trigger, so the record has to exist, and its ID has to be in trigger.new.  So how can I pass a valid ID to the SOQL statement and yet not get a result?  And how is it that this same code has worked in Sandbox before, and is currently working in Production?