I've found out the name of the restaurant I recommended, it's called Gonpachi and it's at 1-13-11 Nishi Azabu, 106-0031, Tokyo. It serves everything from sushi to tempura.
I mentioned it looked a lot like the set of Kill Bill, it turns out with good reason, it's where they filmed Kill Bill.