This is probably because some of your leads that just got inserted don't have record types associated with them. This is normal. You can enforce that record type selection is mandatory through configuration, if that's what you're looking for.
[EDIT]
Now I think I understand the issue (from your comment). The reason is that since you're in a trigger, the associated RecordType referenced object is not available. The RecordTypeId will always be available since it is literally part of the trigger object as an Id. However, child objects (referenced objects) will not be available to simply reference from within a trigger. To do this you need to create a map of the referenced object in question by doing an additional SOQL call WHERE Id IN: theIdList.
From Apex, not in a trigger, you need to specifically call this field out from your SOQL like this:
List<Lead> leads = [SELECT Id, RecordType.Name FROM Lead];
What just happened there is that the child object, the RecordType in this case, was included in the query and therefore available to you. By default a trigger will not have all of your child objects pre-selected and therefore need to be selected afterwards from within the trigger or class called by the trigger:
List<Id> recIds = new List<Id>();
for(Lead l : leads)
{
recIds.add(l.RecordTypeId);
}
List<RecordType> rt = [SELECT Id, Name FROM RecordType WHERE Id IN :recIds];
Map <Id, String> idRecNameMap = new Map<Id, String>();
for(RecordType r : rt)
{
idRecNameMap.put(r.Id, r.Name);
}
// And finally...
for(Lead l : Trigger.new)
{
String tmpRecordTypeName = idRecNameMap.get(l.RecordTypeId);
}
I did not test this code but I think it look ok. Hope this makes sense.