So I've reached 'catalpa' and I looked it up on wikipedia to see what it looked like. However catalpa on English wikipedia and 梓 on the Japanese wikipedia appear to be two completely different trees... I'm not even sure that they're related species.

Obviously this is not really important for my kanji learning, I was just curious if anyone knows why the meaning is catalpa.

Catalpa: http://en.wikipedia.org/wiki/Catalpa
梓: http://ja.wikipedia.org/wiki/%E3%82%A2%E...A%E3%82%B5

Wiki for the (real) Catalpa tree: http://ja.wikipedia.org/wiki/キササゲ - it explains the use of that kanji as follows: "日本で「梓(し)」の字は一般にカバノキ科のアズサ(ヨグソミネバリ)を指すが、本来はキササゲのことである" - maybe Heisig choose this meaning over birch because of the origin of the kanji and because he already named another kanji "birch"?

Maybe its better to learn the (or a?) reading straight from the start? There are quite a few strange trees in the final third of the book (camphor, cedar etc.), and I constantly mix them up. Would anybody of you advanced guys give them a distinct japanese reading?

あずさ is a fairly common reading for 梓, used in names and the like.