Eu tive exatamente os mesmos problemas que você descreve (em um Ubuntu de 64 bits), mas com a impressora LBP7200Cdn. Hoje eu (coincidentemente) encontrei uma nova (er) versão dos drivers Canon CAPT (2.56), incluindo um arquivo debian pré-compilado de 64-bits aqui .
Depois de tentar esta versão, com exatamente os mesmos passos (oficiais do Ubuntu) como eu tentei muitas vezes antes, funcionou imediatamente! Então talvez isso resolva seus problemas (similares) também!