I don't mean to sound flippant but there actually seems to be lots of different hard problems in computer science, or computing (to be honest I'm not sure which we're talking about here) but all of the ones that I know of are hard due to complexity. Our science is good at reductionism, finding fundamentals, but when it comes to complex systems it simply informs our inadequate simulations. So I think the hardest problems in computer science will exist where we try and apply it in the real world to complex machines. In computing there are many hard things to make, databases, operating systems, programming languages, the list goes on - and they are hard because they are big and complicated and so making them is hard because to some extent it doesn't matter how much resource or intelligence you have because the problems that arise in complex systems start to get chaotic and intractable.