Existem dois módulos python chamados magic, com diferentes APIs.
O que o snapcraft requer é empacotado como um deb chamado python3-magic. Este corresponde ao módulo file-magic em pypi: link
O outro é chamado de mágica no pypi: link
Então, se você fizer isso:
sudo pip install magic
Você receberá o errado, e ele será instalado em um caminho que tenha precedência sobre o deb do python3-magic instalado com o apt. Isso é o que causa o erro.
Para verificar se você possui o outro módulo mágico instalado pelo pip:
pip3 list | grep magic
E para removê-lo e corrigir snapcraft:
pip3 uninstall magic