Where Are Those Pesky WoW Cataclysm Instances Hiding?
In order to queue for instances in WoW Cataclysm, it's necessary for the player to actually discover the instance entrance. The instances are scattered throughout most of the new zones - and some of them are hidden, so this can be a challenge.
Introduction to Cataclysm Instance Entrances
The Wrath of the Lich King expansion gave the players of WoW the dungeon finder, a tool that most players have found can be used for both great effect or superb frustration. Cataclysm has added another new wrinkle to the dungeon finder tool - one cannot queue for an instance, or be sent to it on random, without first finding the instance entrance. Perhaps Blizzard's plan is that this encourages exploration and getting to know the lore around the instances better, or perhaps it stands in as a minimum intelligence test for using the dungeon finder. Some of the instance entrances are very well hidden, and how to find Cataclysm instance can be something of a challenge.
There are six brand new instances in Cataclysm, and then new heroic modes for two old Vanilla WoW instances - Shadowfang Keep and Deadmines. It's not necessary to re-find those instances in order to queue for their heroic versions; all that's required is the minimum gear level for a heroic. The six new instances are scattered across several zones.
Important Note: When an instance has been officially "found," text to that effect will appear in the chat box. Until that message is received, the instance will not be counted as found. Occasionally, for mysterious reasons, it takes wandering around or going in and out of the instance a couple of times to actually find it.
Deepholm and Twilight Highlands
These two zones have one Cataclysm instance entrances each, and both are straightforward to find.
In Deepholm, a flying mount is necessary to reach the instance, Stonecore. The instance is located about 2-3 stories above the inn/quest hub in the world pillar. To reach it, simply exit the quest hub, fly up, and then move about a quarter turn around the pillar. There is a ledge with a summon stone on it, and the entrance there leads to the instance.
In Twilight Highlands, Grim Batol is located on the western most edge of the zone, about halfway down the map. There is a cartoon of a stone entrance on the map indicating its location; the entrance itself is at the top of a ramp. There is a quest line in Twilight Highlands that will take the player to the instance entrance. On the Horde side, the quest line starts at Precious Goods. See the WoWhead link for more details on the quest.
Cataclysm Instance Entrances Continued: Uldum
The Cataclysm instance entrances in this zone are all very straightforward, but there's a lot of them - three in one zone.
The Lost City of Tol'Vir acts as a good reference point for the other two instances. Fly south along the river. The lost city sits at the river delta. The instance is in the building closest to the water fall. The building has two entrances, a northern and a southern one. I recommend using the southern entrance; I've entered the instance by running in from the north, and when I did that it didn't give me credit for discovering it.
The Halls of Origination are in the large pyramid that's to the east of the river. The entrance for the Halls is on the east side of the pyramid. The instance entrance itself is a little bit down the hallway that leads into the pyramid.
Vortex Pinnacle also requires a flying mount to get to. It's located high in the air off the coast of Uldum, almost due west of the Lost City of Tol'Vir.
The Throne of the Tides is probably the most annoying instance to reach in the entire expansion. While it is possible to fly in and get to this instance via swimming, that requires being able to breathe underwater for an extended period of time and it's a long swim. It's much less annoying to just do the starting series of quests for the zone to acquire the sea horse mount, or even just one's "sea legs." Once that is done, head for the Abyssal depths using the spiffy new seahorse mount. Go down into the Abyssal Breach, which basically requires going straight downward over the vortex. Entering the vortex causes a fatigue bar to pop up momentarily, but this is normal; a moment later the player is transported into a large cave, which contains the instance entrance.
Searing Gorge/Burning Steppes
Blackrock Caverns seems to be the apology for the never ending, ridiculously long trudge that was Blackrock Depths. In keeping with its ancestral instances, though, this is not one of the easier Cataclysm instance entrances to find.
Start by entering Blackrock Mountain from either from Searing Gorge or Burning Steppes. Once inside, find the entrance along the outer run that has the meeting stone for Blackrock Spire. At the intersection that leads to Blackrock Spire, turn right instead of going straight ahead into the busted door. The entrance of Blackrock Caverns will be visible.
There is also an alternate way of getting to the instance. In Mount Hyjal there is an NPC that starts a quest line; this NPC can teleport you to the entrance of Blackrock Caverns via his mole machine. For more information on that quest line, please see WoWhead.