Why not see what sqlite is doing and do something in C yourself that solves the actual problem. It's not surprising that a general purpose Obj-C (or any language) class isn't terribly fast at one specific thing.
I'd suggest using timegm instead of mktime, or set the TZ environment variable to UTC to ensure all implementations return an identical date. I ran the same tests and found that the strptime was quite fast, but gmtime was taking most of the time. To speed that up, you could borrow SQLite's implementation. Checkout the computeJD function from SQLite's date.c - http://www.sqlite.org/src/doc/trunk/src/date.c
If date formatting is a bottleneck for me (it is surprisingly often, because it's very slow in some languages) I typically just run it through the command-line program 'convdate' [1] from crush-tools, which is more or less just a wrapper around strptime+strftime.
Yes, and that's the workload convdate is intended for: it batch-converts an entire column of a tab-delimited file. The larger crush-tools suite is intended for unix-style batch processing of tabular data, but fills in some functionality that the classic set of POSIX tools (cut, sort, paste, join, etc.) didn't cover.
strptime_l took 58.803 seconds
NSDateFormatter took 107.570 seconds
sqlite3 took 7.022 seconds
And with MishraAnurag's suggestion of using timegm instead of mktime:
strptime_l took 21.656 seconds
NSDateFormatter took 108.163 seconds
sqlite3 took 7.096 seconds