Wine es una implementación de la API de Windows para sistemas *X (sistemas basados en UNIX). A no confundirse, no se trata de un emulador, ya los programas corren nativamente, de ahí el acrónimo recursivo de su nombre "Wine Is Not an Emulator".

En mi caso lo instalé sobre un Hardy Heron de Ubuntu, y como era de esperarse, no tuve ningún inconveniente (lo más dificil, como siempre fue escribir sudo apt-get install...,)

$ sudo apt-get install wine
Leyendo lista de paquetes... Hecho
Creando árbol de dependencias       
Leyendo la información de estado... Hecho
Se instalaron de forma automática los siguientes paquetes y ya no son necesarios.
  linux-headers-2.6.24-16-generic linux-headers-2.6.24-16
Utilice «apt-get autoremove» para eliminarlos.
Se instalarán los siguientes paquetes extras:
  binfmt-support libaudio2
Paquetes sugeridos:
  nas msttcorefonts
Se instalarán los siguientes paquetes NUEVOS:
  binfmt-support libaudio2 wine
0 actualizados, 3 se instalarán, 0 para eliminar y 0 no actualizados.
Necesito descargar 11,8MB de archivos.
Se utilizarán 55,3MB de espacio de disco adicional después de desempaquetar.
¿Desea continuar [S/n]?
Des:1 http://ar.archive.ubuntu.com hardy/universe binfmt-support 1.2.10 [21,4kB]
Des:2 http://ar.archive.ubuntu.com hardy/main libaudio2 1.9.1-1 [79,2kB]
Des:3 http://ar.archive.ubuntu.com hardy-updates/universe wine 0.9.59-0ubuntu5 [11,7MB]
Descargados 11,8MB en 17min48s (11,1kB/s)                                               
Seleccionando el paquete binfmt-support previamente no seleccionado.
(Leyendo la base de datos ... 
158780 ficheros y directorios instalados actualmente.)
Desempaquetando binfmt-support (de .../binfmt-support_1.2.10_all.deb) ...
Seleccionando el paquete libaudio2 previamente no seleccionado.
Desempaquetando libaudio2 (de .../libaudio2_1.9.1-1_i386.deb) ...
Seleccionando el paquete wine previamente no seleccionado.
Desempaquetando wine (de .../wine_0.9.59-0ubuntu5_i386.deb) ...
Configurando binfmt-support (1.2.10) ...
 * Enabling additional executable binary formats binfmt-support                   [ OK ]

Configurando libaudio2 (1.9.1-1) ...

Configurando wine (0.9.59-0ubuntu5) ...

Processing triggers for libc6 ...
ldconfig deferred processing now taking place
$
$

Una vez instalado, en el menún principal agregó el submenu Wine y en el home de mi usuario el directorio .wine\drive_c con las clásicas carpetas de Windows: Archivos de Programa y Windows.

Además, ya desde el menú, se agregó el submenú Programs, con el acceso al Bloc de Notas, y los elementos Browse C:\drive (que representa el directorio .wine\drive_c), Configure Wine y Unistall Software.

Para correr un binario de Windows puedes crear el acceso directo, o desde consola ejecutar, por ejemplo: wine regedit.exe

Por lo tanto, si no puedes reemplazar o estás obligado a correr algún programa de Windows, con Wine probablemente encuentres la solución al "problema". Sinó, mira: