The issue was that I was C methods to determine the data length:
CCHmacContext ctx;
CCHmacInit(&ctx, kCCHmacAlgSHA1, keyBytes, strlen(keyBytes));
CCHmacUpdate(&ctx, baseStringBytes, strlen(baseStringBytes));
CCHmacFinal(&ctx, digestBytes);
It worked consistently when I used the NSString/NSData length methods:
CCHmacContext ctx;
CCHmacInit(&ctx, kCCHmacAlgSHA1, keyBytes, [key length]);
CCHmacUpdate(&ctx, baseStringBytes, [data length]);
CCHmacFinal(&ctx, digestBytes);
Edit:
As mentioned by Ivo Beckers
in the comments, this can also be written as a single line:
CCHmac(kCCHmacAlgSHA1, keyBytes, strlen(keyBytes), baseStringBytes, strlen(baseStringBytes), digestBytes);