VLC reproduce imágenes alargadas y en blanco y negro [Solucionado]

Muy buenas, amigos.
Ayer instalé el paquete openjdk-6-jdk, que leí que era necesario para Jdownloader y aptitude me advirtió de que se eliminaría un paquete. No recuerdo exactamente cuál era, pero se parecía algo así como a "radeon {n}". Acepté y me olvidé.
Ahora quiero ver un archivo .avi con VLC y sobre el fondo negro de la pantalla, la imagen se "estrecha" y ocupa un 25% del total de la imagen que debería, como si estuvies "comprimida" y estirada, estilo El Greco. Además, no aparecen colores.
Tengo una tarjeta ATI y supongo que todo está relacionado con la eliminación de ese paquete. Ingenuamente, pienso que bastaría con instalarlo, pero no sé si Debian guarda una lista de paquetes borrados últimamente.
A continuación os detallo la salida de algunos comandos:

pere@solaris:/home/videos$ vlc 001.avi
VLC media player 1.1.3 The Luggage (revision exported)
Blocked: call to unsetenv("DBUS_ACTIVATION_ADDRESS")
Blocked: call to unsetenv("DBUS_ACTIVATION_BUS_TYPE")
Warning: call to signal(13, 0x1)
[0x89698fc] main libvlc: Ejecutar VLC  con la interfaz predeterminada. Use «cvlc» para usar VLC sin interfaz.
Blocked: call to setlocale(6, "")
Blocked: call to sigaction(17, 0xb67380d4, 0xb6738048)
Warning: call to signal(13, 0x1)
Warning: call to srand(1298068223)
Warning: call to rand()
Blocked: call to setlocale(6, "")

(process:4533): Gtk-WARNING **: Locale not supported by C library.
Using the fallback 'C' locale.
Warning: call to signal(13, 0x1)
Warning: call to rand()
Warning: call to rand()
Warning: call to rand()
swScaler: pal8 is not supported as output pixel format
[0x8da65dc] swscale scale error: could not init SwScaler and/or allocate memory
[0x8db85f4] xcb_xv generic error: no available XVideo adaptor

olaris:/home/pere# dmesg | grep radeon
[    6.145094] [drm] radeon kernel modesetting enabled.
[    6.145547] radeon 0000:03:00.0: PCI INT A -> Link[APC4] -> GSI 19 (level, high) -> IRQ 19
[    6.151333] [drm] radeon: Initializing kernel modesetting.
[    6.152697] radeon 0000:03:00.0: putting AGP V3 device into 8x mode
[    6.152710] [drm] radeon: VRAM 128M
[    6.152714] [drm] radeon: VRAM from 0x00000000 to 0x07FFFFFF
[    6.152718] [drm] radeon: GTT 64M
[    6.152722] [drm] radeon: GTT from 0xE0000000 to 0xE3FFFFFF
[    6.152771] [drm] radeon: irq initialized.
[    6.153249] [drm] radeon: 128M of VRAM memory ready
[    6.153254] [drm] radeon: 64M of GTT memory ready.
[    6.153527] [drm] radeon: 1 quad pipes, 1 Z pipes initialized.
[    6.153546] [drm] radeon: cp idle (0x10000C03)
[    6.154355] platform radeon_cp.0: firmware: requesting radeon/R300_cp.bin
[    6.367163] radeon_cp: Failed to load firmware "radeon/R300_cp.bin"
[    6.367298] radeon 0000:03:00.0: failled initializing CP (-2).
[    6.367355] radeon 0000:03:00.0: Disabling GPU acceleration
[    6.367416] [drm] radeon: cp finalized
[    6.367650] [drm] radeon: cp finalized
[    6.368335] [drm] radeon: ttm finalized
[    6.369396] [drm] radeon: VRAM 256M
[    6.369400] [drm] radeon: VRAM from 0x00000000 to 0x0FFFFFFF
[    6.369404] [drm] radeon: GTT 512M
[    6.369408] [drm] radeon: GTT from 0x20000000 to 0x3FFFFFFF
[    6.372187] [drm] radeon: irq initialized.
[    6.390753] [drm] radeon: 128M of VRAM memory ready
[    6.390758] [drm] radeon: 512M of GTT memory ready.
[    6.393866] [drm] radeon: 1 quad pipes, 1 Z pipes initialized.
[    6.393879] [drm] radeon: cp idle (0x10000C03)
[    6.396327] platform radeon_cp.0: firmware: requesting radeon/R300_cp.bin
[    6.402107] radeon_cp: Failed to load firmware "radeon/R300_cp.bin"
[    6.402235] radeon 0000:03:00.0: failled initializing CP (-2).
[    6.402293] radeon 0000:03:00.0: Disabling GPU acceleration
[    6.402353] [drm] radeon: cp finalized
[    7.071892] fb0: radeondrmfb frame buffer device
[    7.078725] [drm] Initialized radeon 2.0.0 20080528 for 0000:03:00.0 on minor 0
pere@solaris:/home2/rafa/videos$ xvinfo
X-Video Extension version 2.2
screen #0
no adaptors present
pere@solaris:/home2/rafa/VIDEOS/BEACH$

Agradezco vuestra atención, saludos

que raro porque observando el conflicto del paquete dice:

Tiene conflictos con: openjdk-6-jre (< 6b17~pre3-1), openjdk-6-jre-headless (< 6b17~pre3-1)

osea no elimina radeon* ni mucho menos...
tu sistema esta actualizado al día?
postea esto:

aptitude search radeon

y fijate si tienes instalado firmware-linux-nonfree que tiene el firmware para la R300:

aptitude search firmware-linux-nonfree

de donde tenes instalado el vlc?

1) proba purgar el vlc

2) con locate elimina todo rastro de el vlc anterior (TODO ... hasta lo que hay en tu /home/.config y .cache)

3) Instalate el VLC desde los repositorios multimedia ... o hace un pinning desde experimental

saludos..

Hola damian_sima y Wasmosy. Todo fue a partir de un update y upgrade que hice el Domingo. Ayer volví a hacer un update y upgrade y ya no tengo problemas con los vídeos, todo vuelve a la normalidad. Gracias por la respuesta. Adjunto los comandos que me dijiste, damian:

pere@solaris:~$ aptitude search radeon
i A libdrm-radeon1                  - Userspace interface to radeon-specific ker
p   libdrm-radeon1-dbg              - Userspace interface to radeon-specific ker
p   radeontool                      - Utilidad para controlar las funciones de r
i A xserver-xorg-video-radeon       - X.Org X server -- AMD/ATI Radeon display d
p   xserver-xorg-video-radeon-dbg   - X.Org X server -- AMD/ATI Radeon display d
i A xserver-xorg-video-radeonhd     - X.Org X server -- AMD/ATI r5xx-r7xx altern
p   xserver-xorg-video-radeonhd-dbg - X.Org X server -- AMD/ATI r5xx-r7xx altern
pere@solaris:~$ aptitude search firmware-linux-nonfree
p   firmware-linux-nonfree                                        - Binary firmware for various drivers in the Linux kernel    

Saludos a todos y muchas gracias clap clap