This could just be a case of needing to optimize and train their recognizer to deal with a much larger set of possible characters, or it could require implementing kanji-specific OCR techniques like attempting to decompose the characters into their constituent strokes, and recognize based on classification of those strokes (orientation, position, direction).
Of course, guessing the correct word when performing word-for-word translation of hanzi is almost impossible, so even the extremely primitive product I'm thinking of is very difficult.
On the other hand, an English to Chinese translator might be more doable, and might also be more commercially profitable.
An app that converted from characters to pinyin (a much easier problem) would be gold to someone trying to learn mandarin. I'd easily pay $50 for something with that functionality without it even making an attempt at the english. It's a much smaller market than those trying to understand chinese signs on a vacation, but it's one with a much larger stake and interest in the result.
Here's a video demo: http://www.youtube.com/watch?v=x7VTo0656Rc