List of np-hard problems in biology/bioinformatics
I'm no expert in computational biology but I am very much interested and do some big data analysis using R for my own projects so I will try to provide some information.

This (http://www.ncbi.nlm.nih.gov/books/NBK25461/) is an excellent book talking about all the grand challenges in computational biology and the emerging fields so I definitely recommend looking through at least the list on the page, if you don't want to read the entire book. To me all this points to the fact that we are in the big data era, where we have masses of data but making sense of them all and putting them into prospective and analysing them in a way to show us new insights into problems is difficult.

You might also be interested in BOINC, which runs a few computationally challenging projects through crowd sourcing/grid computing (http://boinc.berkeley.edu/projects.php). In more theoretical aspects, here is a list of unsolved problems (http://en.wikipedia.org/wiki/List_of_unsolved_problems_in_mathematics), solving of which will excel our understanding of many modelling problems, which percolate in biological problems as well although I'm not at all an expert in biological systems modelling.

Hope this helps!