# GolfScript, <s>112</s> 108 characters

    [{}/]{97-}%:s;"etaoinshrdlcumwfgypbvkjxqz"[{}/]{97-}%:f,:&,{:x;[s{&x-+&%f?}%{+}*x]}%$0=1=:x s{&x-+&%97+}%''+

I'm not happy about the repetition with the string processing and 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+}%''+