Another thing to point out I think is that the Japanese themselves have some problems with kanji, as the use of computers seems to have an effect on the way that people use and remember the kanji.
You'll see shows on television that are like language quizes for different talent as a sort of edutainment program.
Many Japanese people I've known have told me that they knew off hand around 500 or so kanji rather than the 2000 expected by the Ministry of Education as 'daily use' kanji.
I've always read good things about Japanese lessons that emphasise use of the kanji early, I think this is also a good way to learn them, by seeing them in context.