Eu tive o mesmo problema com o Firefox 20.0.1. Resolvi quando vi minha senha do Sync salva no Firefox ( Opções - > Segurança - > Senhas salvas - > Mostrar senhas ) não é o mesmo que eu digitei quando configurei o Sync. Alguns caracteres especiais (como é ) foram substituídos por outros caracteres.
Resolvi o problema alterando minha senha e usando apenas a-z A-Z 0-9 caracteres.
(Eu arquivei um bug aqui )