Then I saw this video, and started learning Japanese.
It was probably Capcom X Namco (read X as cross), which is the first in this series. It was on PS2 and has an english fan patch if you know how to do that sort of thing (kind of like what you do to get Final Fantasy XII: Zodiac Job System to work). The two original characters from that game are in this as well (that would be the guy and gal with the katana/gun sets).I seem to recall seeing gameplay footage of a game just like this a couple of years ago. Not sure what system, but whatever it was, it never came to the US. I'm thinking it may be the same with this.