Однажды у меня было много проблем именно с такой проблемой, пока я явно не установил форматер в en_US locale. systemLocale НЕ хорош, потому что это может быть что-то отличное от en_US, влияющее, например, на названия месяца / дня недели и т. д. Это часть рабочего кода:
NSDateFormatter *fmt = [[[NSDateFormatter alloc] init] autorelease];
[fmt setDateFormat:@"eee MMM dd HH:mm:ss Z yyyy"];
[fmt setLocale:[[[NSLocale alloc] initWithLocaleIdentifier:@"en_US"] autorelease]];
NSDate *formattedDate = [fmt dateFromString:someStringContainingDate];