Once you play through Hell on Earth you get the achievement for it. Then you have to also play the other part of the story that is the No Rest for the Living and then you get the achievement for it and if you have played through them both on UV you'll get the achievement for it.
Hell On Earth and No Rest For The Living are not the same thing. Hell on Earth has 32 levels and No Rest For The Living has 9 levels. If I remember correctly when you start a new game it asks you if you wanted to play hell on earth or no rest for the living and then to choose difficulty. You have to play hell on earth and No rest for the living and have a save file for both of them.
Thanks to Rep for this sick picture!