Podría ser un problema de los repositorios
Antes de nada, actualizalos con
sudo apt-get update y
sudo apt-get upgrade.
Después, si no te ha dado ningún error, prueba a instalar el paquete en cuestión a través de la consola:
sudo apt-get install paquete
En lugar de paquete, tendrías que poner el nombre del paquete que quieres instalar, por ejemplo wine. Prueba a ver que te dice.