While I am not an expert on the shuttle flight software, these are some challenges in flight software in general: Consider the problem of orbital insertion around a moon of saturn, or around an inner planet, or an asteroid. Not only does the guidance and control subsystem have to react (i.e., actuate the thrusters whose thrust can vary by orders of magnitude) within a razor-thin margin, but each scientific instrument has requirements as well, and introduces its own perturbations (e.g., extension of an antenna boom causing vibrations). Plenty of PhDs, and PhD topics to be found in this and associated problems. ANother example, consider space network links. You can't just use TCP (it's been tried, and it simply breaks down), you need to engineer a protocol -- in fact a whole new suite of protocols -- from the ground up that provides the same reliability but over much faultier links. Although TCP is simple in concept (just ACK/NACK till you got everything, right?), 30 years of its evolution shows that it is anything but. Both of these problems necessarily involve some bending of the mind to solve, and I image there are related ones for the folks in the manned-space sector

EDIT: and among other things that I'd consider important to mention, there are significant robotics challenges, autonomous behavior and decision making (with associated problems in formal model verification), along with the general high degree of fault tolerance required in just about every software (and hardware) subsystem. I think many of the hardest problems in CS can be found in the spaceflight domain.