Did some more digging and I apparently found the solution. I simply got rid of AVEncoderBitRateKey and everything works fine. So now my recordSettings dictionary looks like this:
// Setup audio recording
NSDictionary *recordSettings = @{AVFormatIDKey: @(kAudioFormatMPEG4AAC),
AVEncoderAudioQualityKey: @(AVAudioQualityLow),
AVNumberOfChannelsKey: @1,
AVSampleRateKey: @22050.0f};
Still not sure why this would be the case only on an iPhone 5S. Again, I've tested on all other devices running iOS6 and iOS7, and the old settings dictionary works fine on everything except for the 5S. Now that I've removed the AVEncoderBitRateKey and value, it also works on the 5S.