I've defeated both of the lieutenants of the Sorcerer King. The quest says that I need to take my best army to defeat the sorcerer king.
The only problem is that the gate is still impasable. I have both keys and have defeated all the Sorcerer King's troops.