Is the food served at a non-kosher, non-Jewish run sushi restaurant considered non-kosher because of the non-kosher-ness of the knives, the bishul akum of the rice, or both?
Both of these problems that you mentioned, as well as others, are issues. Bishul akum would probably be more of an issue than the knives since they would always be used on cold things and are probably washed; however, the knives may have been used on foods with a sharp taste (such as an onion), which renders temperature irrelevant, although you could get around this problem by ordering something that does not have any of these sharp-tasting foods in it. Food items subsequently cut with that knife are not rendered unkosher. Also, you can't really know that they're always washed between treyf and kosher fish.
That is the more general problem anyway with non-kosher restaurants. You just don't really know what's going on the kitchen, so it's hard to justify eating there even if all of the ingredients used in the restaurant are kosher.