Ok looks like it's an RTFM issue (hopefully). After installing the tumblog (or WooThemes supported Tumblog) you need to go to Settings > Permalinks and save your permalink structure again. This re-registers the custom taxonomies with the Tumblog plugin.
Here's the reference from WooThemes Tumblog Support: http://www.woothemes.com/support/wootumblog/
Now the question is: did it work?