Quem tiver o mesmo problema, fiz o seguinte:
No mesmo lugar que criei a paper wallet (bitaddress.org) fui em "wallet details". Lá é possivel desencriptar a chave privada. Bastou colocar minha chave privada encriptada, coloquei a senha, e ele me deu a chave privada original. Copiei, colei na Electrum, e problema resolvido.
Vlw
Show, que bom que conseguiu resolver. Vai servir de ajuda.
Pergunta: para desencriptar a private key você precisou de estar conectado à internet?
Ah, recomendo transferir o saldo para outra wallet, visto que sua pk já não é mais "anônima"