The Cataclysm has wrought changes to many facets of Azeroth and the dungeons found across the world are no exception. As many of the zones throughout the world now have new level ranges, the dungeons within their borders have been adjusted to match, and the items that drop within those dungeons have had their stats changed accordingly.
Here's a list of all 1-60 dungeons and the level range at which each should be explored, followed by the minimum level required for entry in parentheses.
In order by minimum level to enter.
The Deadmines
Level Range: 15-21 (10)
Ragefire Chasm
Level Range: 15-21 (10)
Wailing Caverns
Level Range: 15-25 (10)
Shadowfang Keep
Level Range: 16-26 (11)
Stormwind Stockade
Level Range: 20-30 (15)
Blackfathom Deeps
Level Range: 20-30 (15)
Gnomeregan
Level Range: 24-34 (19)
The Scarlet Monastery - Graveyard
Level Range: 26-36 (21)
The Scarlet Monastery - Library
Level Range: 29-39 (21)
The Scarlet Monastery - Armory
Level Range: 32-42 (21)
The Scarlet Monastery - Cathedral
Level Range: 35-45 (21)
Razorfen Kraul
Level Range: 30-40 (25)
Maraudon - Purple Crystals
Level Range: 30-40 (25)
Maraudon - Orange Crystals
Level Range: 32-42 (25)
Maraudon - Pristine Waters
Level Range: 34-44 (25)
Uldaman
Level Range: 35-45 (30)
Dire Maul - East
Level Range: 36-46 (31)
Scholomance
Level Range: 38-48 (33)
Dire Maul - West
Level Range: 39-49 (34)
Razorfen Downs
Level Range: 40-50 (35)
Dire Maul - North
Level Range: 42-52 (37)
Stratholme - Main Gate
Level Range: 42-52 (37)
Zul'farrak
Level Range: 44-54 (39)
Stratholme - Service Entrance
Level Range: 46-56 (41)
Blackrock Depths - Prison
Level Range: 47-57 (42)
The Sunken Temple
Level Range: 50-60 (45)
Blackrock Depths - Upper City
Level Range: 51-61 (46)
Lower Blackrock Spire
Level Range: 55-65 (48)
Upper Blackrock Spire
Level Range: 55-65 (48)