Não tenho certeza se devo responder minha própria pergunta, mas consegui resolver o problema.
Como o erro no log mencionou uma nota chamada "New Note Template", criei uma nota com esse nome através do site do Ubuntu e tentei sincronizar novamente. Desta vez tomboy detectou o conflito e ofereceu algumas opções para resolvê-lo. Eu escolhi renomear a nota local e então sincronizar todas as minhas notas corretamente!