I'm chinese, have been to japan, and I took a year woth of japanese credit in college. my GF is half-japanese also. I am from San Jose and one of the more popular japanese resturants that I know up there is "MIYAKE" .....I think thats what it was called..
Anyways, if it was my resturant, I would name it with a "fish" theme. Not necessarily have to be of a japanese word.
Here are some names:
"SALTWATER" - Conjures up images of sea life (fish, shrimp, crab, etc)
"MIAKO" - I just happen to like this name, plus i know someone with this name
"TAIKO" - a very famous japanese restaurant here in Irvine. I'm sure you can use it though, b'c its not a chain restuarant
"MISHIMA" - another very nice/fast japanese restuaramt in Beverly Hills
or perhaps you can name it after japanese based movies: RASHOMAN, SAMURAI (sorta corny), etc.....
but since its a beninhana type resturant, you would probably want a name that is very festive:
Click here for major japanes festivals
Well, I would expect a free meal if you use those names..hope it helps..enjoy!