原因を追求してみたにょ。
base64コデックのdecode()がunicodeオブジェクトではなく
stringオブジェクトを返すのが原因だったにょ。
漏れの考えではこれはバク（仕様違反）にょ。
次のように修正すると動くようになるにょ。

× output = base64.decodestring(input)
○ output = unicode(base64.decodestring(input), "iso-8859-1")

>>645
調べてみて分かったんだけど、デコードの対象になるのは
エンコーディグ指定の行よりも後の行だけみたいだにょ。
よって、

# coding: base64
aW1wb3J0IHN5cwoKcHJpbnQgc3lzLmFyZ3YK

はOKだけど、

# coding: base64
# by 640
aW1wb3J0IHN5cwoKcHJpbnQgc3lzLmFyZ3YK

はNGにょ。