Eu uso o mesmo mouse com o Mint 14 (baseado no Ubuntu), e ele nunca funciona a partir de uma inicialização, mas desconecte e reconecte o receptor USB e ele funciona perfeitamente.
Eu normalmente 'suspendo' em vez de 'shutdown', e sempre funciona bem quando eu 'retomar', então o problema parece estar na inicialização inicial. Eu não investiguei mais, pois a solução é tão rápida e simples.