Creating this more as something to perhaps follow up with TomTom's author.
As previously stated TomTom doesn't work in the DK starter area. However with Cataclysm there are more phased zones being introduced - namely the worgen (and goblin - I forgot to check, but I assume so) starter areas.

I haven't tested with any addons in Cat yet, but I'm assuming the problem still persists (I haven't seen an updated TomTom for Cataclysm yet).

Yeah, I'm thinking TomTom's author will have to fix this issue in Cata. Basically, this happens if the zone in question doesn't exist on the normal mapped zones. So the DK zone, the two goblin starter zones, and Gilneas all should apply.

Cladhaire basically said that his addon is based on another library, which needs to be updated before this support can happen. However, he thinks that most cataclysm zones won't suffer from this problem - apparently the issue is because the DK starter zone is sort of part of another zone or used to be a different zone or something.

Since it seems likely that this will get fixed on its own, I'm going to close this issue for now to save room on the issue list.

Oh, since nobody complained so far, you can also let him know that his idea for the autocomplete step worked well, using the callback functions!

Oh yeah! I need to thank him for that. Thanks for the reminder :)

I just left a message on TomTom's comment board asking about this.