Apple can do whatever it wants. I don't think Apple ever promised anyone the AppStore would be fair, and Apple has routinely denied apps for features implemented in the OS later. They can do this, but I think it's wrongheaded in this case, and a bit harmful to Apple in the long term.
First, f.lux isn't asking for root access. All Apple has to do is open up one interface command that allows apps to adjust hue, and to run in the background. Just like Spotify playing music in the background all day long doesn't require root access, just like Facebook pulling updates in the background doesn't require root access, just like Flickr auto-uploading photos soon after I take them automatically doesn't require root access.
The problem is not doing stuff in the background. Apps can upload stuff in the background but they have a time limit, apps can play music in the background but it won't affect the sounds of the game you are playing because the foreground app will always override any background sound if it wants to play sounds.
The problem is doing things in the background constantly (which the user does not notice like he or she would do with music playing) and that affect the output of other apps (ie, how colours are displayed).
Furthermore, hue adjustment can be added to the list of security privileges in iOS. Just like users have to approve apps access to location or photos or address book or whatever, they would approve access to "night shift".
Sure, but to give third-party apps access to Night Shift, Apple first has to create Night Shift (which it is doing with iOS 9.3). And at that point, you would have a third-party app offering a different UI for a system setting, which is generally a bit of a hack (like, eg, third-party apps being allowed to change the display resolution on OS X). And there is a big difference between read and write access (location, photos, address book are largely read access only, eg, while you can add photos you cannot delete photos via third-party apps). Getting read access to data is quite different than altering the (screen) output of other apps.
Second, f.lux is clearly interested in developing this feature to a more advanced and complicated level than simple sun-rise to sun-set schedule, with a constant hue adjustment. They want access to the part of the iOS user-base that is ready and willing to use their app in order to take this idea to the next level. Just spitballing here: Maybe they can use the front-facing camera and light-sensor to detect the kind of lighting in your room and automatically adjust the hue dynamically? Maybe they can automatically determine your sleep schedule from your usage pattern and set the hue-adjustment schedule that way? Maybe they have much better ideas? Either way, I don't see how it harms users nor Apple to let them do this.
Sure, those might be good ideas, but can you give me one precedent where a third-party app is allowed to change system settings on iOS?
And there is the simple rule that what you do in one app should never break how things work in another app. That is the foundation for the general populace being able to install anything they want without having to fear anything happening outside the (besides using resources like bandwith, disk space or energy).
Why not let them make a ResearchKit app or something to let them experiment on willing users, just like Apple touts in their ads? Worst-case scenario, it's a waste of time. Best-case scenario is f.lux discovers something good. They can't brag about how much potential there is for scientific and medical research there is on iOS, and then in the same breath deny access to a legitimate and popular company doing research in a medical area for no good reason.
That could be a good idea but I don't think that is what f.lux wants. If they wanted this, they could have plainly said so.
Finally, Apple has this bad habbit of cutting out apps while implementing the same feature. They are totally within their right to do so, but doing so always erodes developer confidence just a bit, and doing so always spends a little bit of Apple's hard-earned good will. I don't think it's worth it.
Sorry, that is a side-effect of reality. You simply cannot prevent OS makers from adding features. That's like disallowing companies to fire people, that is not how a market economy works.