Here's what I've collected from screenshots and other. I'm not in the Beta myself:

*SPOILERSSPOILERSSPOILERS*




CHARACTERS:
1. Turalyon: Missing, presumed dead. A conversation shows that his SON(!) is determined to search for him. Chances of him being actually dead: 0%
2. Khadgar: Alive, presumed awesome. He's been studying with the Naaru -- and apparently learning a lot!
3. Hemet Nesingwary: Now in Outlands! He's looking for some big game, and needs your help. Appears to be both Horde and Alliance now.
4. Uther: Still dead. But on the plus side, he appears as a ghost after you help his tomb in WPL.

ZONES:
1. Hellfire Peninsula: The eastern portion appears to be a continual war between the Burning Crusade and Alliance/Horde. A fragile Horde/Alliance truce prevails directly at the area, but nowhere else.
2. Auchindoun: Apparently we're getting a reprise of the Sunken Temple storyline. A outcast mourns for his cultist race, who are worshipping a sort of god.

OTHER:
1.

I'll collect and post them here.

I'll post some more as I find them

Hemet Nessingway has always been Horde & Alliance...

Force Commander Danath Trollbane is in the game, having survived the end of Beyond the Dark Portal. He appears to think (from his spoken text) that Turalyon and Khadgar are both "lost to the void." Note: You won't recognize him from his face, as he has aged significantly and now has a full beard.

Edit: Evidently Tigole has stated that we'll be encountering all of the Expedition heroes in one way or another during the expansion's storyline. Also, there is a BE lowbie quest which involves you returning to Sylvanas the amulet inscribed to her from Alleria, her sister.

Alleria should be interesting to meet. If anyone has an indentity crisis, it's going to be her. Alliance hero, (assuming she is) now a Blood Elf would make her technically Horde. I guess that might depend if she's alive or you'll simply see her spirit. I can't imagine the heroes would be very friendly towards the Horde considering the sacrifices they made to stop them.

Danath Trollbane is in Honor Hold. And the Wildhammer guy is in Shadowmoon Valley.

I never played Frozen Throne, I have no idea who you guys are talking about. :(

You wouldn't have have even if you played Frozen Throne, most of the names mentioned are from the expansion of Warcraft II; Beyond the Dark Portal. Which is fitting, considering we are going beyond the dark portal and all.

But cool to see the names back. Wonder if we're going to see some of the Horde heroes too, though they'd be more liable as bosses in instances than anything else as the Horde was still evil back then.

From beta fourms:

You can go in now(Caverns of Time). First you have to complete a quest with a tourguide that shows you around. Its slow and boring, but whatever.

As stated before there are 3 instances: Old Hillsbrad, The Dark Portal and Mt. Hyjal.
You have to do them in order. What I mean is you cannot zone into Dark Portal without rescuing Thrall in Old Hillsbrad first. So I guess you cant zone into Mt. Hyjal without doing the other 2 first.

Old Hillsbrad is funny as hell. Dont go near Tarren Mills there are lvl 67 elites that will aggro.
Go to Southshore and and look at all the famous NPC's!!!!

NPC's I saw in Southshore:
Nat Pagle
Kel Thuzad
Herod (small boy named Herod the Bully)
Capt. Haines and Capt. Sanders (I think these are sailors from a Wetlands quest?)
Highlord Mograine
Tirion Fordring
Taelan Fordring
Stalvan (yes they guy from the Duskwood questline)
Mograine's son (the one you have to find in Outland to get the Ashbringer)
Nathanos the Blightcaller

Wow. I've played WC 1,2 and 3, never even knew there was an expansion for WC2. I'm gonna be all sorts of confused.

I hope some of the heroes retain their catchphrases in some manner, ie: "Touch me again and you'll pull back a stump".
It was significantly harder than the original WC2 campaign and quite a lot of fun.

Hmm, weird. I wonder how they feed their magical addictions, then. I imagine them to be pale and shaking uncontrolably :p