I get "not enough energy" when I try to teleport and my energy (red) and fatigue (blue/mana) are at max levels. And I have been using Teleport several levels.
*groan* you've probably found yet another quirk, I don't have teleport so I can't help out, maybe you need to rest in an inn one time before every teleport?
Well I assume you have enough fatigue for one teleport if you've been using it for several levels. Noone else seems to have this problem so just load up an earlier save.