GolfScript, 112 108 102102 100 characters
{[{}/]{97-}%}:b~:|;"etaoinshrdlcumwfgypbvkjxqz"b:f,:&,{:x;[|x[|{&x-+&%f?}%{+}*x]*\]}%$0=1=:x|{&x-+&%97+}%''+
I'm not happy about the repetition with the re-decrypting at the end, but meh.
Ungolfed (if that makes any sense :P) and slightly older version:
# store input IDs (a = 0, b = 1, etc.) in s
[{}/]{97-}%:s;
# store frequency data IDs in f (blah, repetition)
"etaoinshrdlcumwfgypbvkjxqz"[{}/]{97-}%:f
# for each number from 0 to 26 (length of previous string left unpopped)...
,,{
# the number is x
:x;
# return an array of...
[
# the score
s{x 26\-+26%f?}%{+}*
# and the n
x
]
}%
# use $ort to find the n to output
$0=1=:x
# get the string that the n corresponded to (blah, more repetition)
s{x 26\-+26%97+}%''+