If they hadn't ran a dungeon since the 3 tiers were added, but had completed enough to fulfill the requirements, it's possible. Similar to the kill x mobs achievements - you may have killed 500,000 before a 'kill 500,000' is added. So when you log on, and kill a mob (now your 500,001 mob) you will activate the achievement.