The question Bioinformatics and Graph Algorithms lists a number of important graph algorithms, and frankly most of them don't have easily accessible solutions with GPU based implementations.

The biggest "unsolved" problem is SAT. Write a good GPU SAT solver and the model checking community will get on their knees in praise.

http://www.satlive.org/

Here is the link for a recently published GPU-MSA: http://gpualign.cs.put.poznan.pl/