I think I can explain what you're encountering with a diagram. o is your wizard. x is where you're attempting to teleport to. The | and `` are walls.
If you attempt to do this, you will simply faceplant against the wall and burn your cooldown. Even if you're baarely on the edge of the corner of the two walls. The same thing apples to other more subtle barriers which can make wormholing around the map annoying. The worst part is it even used to apply to stairs, which made it horrendous.
This was true in 1.0.7, but I don't think this is the case any more. They significantly improved Teleport with patch 1.0.8. As long as there's a clear path from you to your target, and your target is within Teleport's range, you should be able to get there. For example:
That said, Diablo 3's Teleport algorithm is still much more finicky than the one in Diablo 2. Diablo 2 would always attempt to move you as close to your target as possible, even if that meant moving you a little to the left or the right of your destination, or even beyond your sight range. Diablo 3 will not help you in the slightest. It will only ever move you in a straight line, and if your destination is unreachable, faceplant you onto a wall.
Even with the 1.0.8 improvements, teleporting through closed doors (in Keeps, for example) is still very much impossible, and as you said, stairs are problematic. The stair issues are caused by Diablo 3 misinterpreting what you're aiming at. It may look like the stairs are going down, but if you click on a floor that's far below you, you're actually not clicking on the floor, but on a piece of air above the floor, at your height. The best place to demonstrate this is Heart of the Cursed. I want to go to the bottom of the stairs, so that's where I'm aiming: http://img24.imageshack.us/img24/9752/b0p7.jpg
But instead, I almost fall off the edge of the world: http://img545.imageshack.us/img545/3279/dfiw.jpg
This is because the engine doesn't believe there's a straight line between the top and bottom of the stairs. It tries to draw a straight line from my toon to the cursor, as if the cursor were positioned at the same height
. In so doing it draws a line through the scene that is not actually a line that goes down the stairs, but cuts a curved shape along the landscape that falls off the stairs on the left.
I tried to make a drawing to illustrate this principle, but my artistic skills are truly embarrassing. Instead, have this: where you actually have to aim is at a point that's above the spot you want to teleport to
This is not specific to Teleport. The same principle applies to walking and aiming your attacks: http://img14.imageshack.us/img14/4055/fkue.jpg