General :: Unable To Boot Debian - PANIC - Double Fault

I recently decided to build up a Linux computer with the following configuration:
- Motherboard : MSI KT4 Ultra
- CPU : Athlon XP 2000+
- RAM : Kingston ValueRAM (2 DIMMs, I put them in all possible arrangements)
I doubt other compoment details are relevant, but if you do think so, feel free to ask.

I installed Debian 5.05 on that machine ; it worked all fine.

However, given that my mobo would not support wake on lan (and that I needed it given that my goal was to build some sort of server), I searched for a new one that did, I then installed an ASRock K7S41GX.

Since doing so, I have not been able to boot Linux ; after doing some fixing on my part, I have come to the point where I have the very same error repeating times and times again every time I try to boot ; here's the error message I get and how I get to it.

GRUB loads like a charm, then Linux starts booting and stuff happens :

Checks filestystem, initrd and stuff (I actually don't understand that part, but it seems to work OK).

Where "########" stands for a series of eight hexa chars (I assme these might be memory adresses ?).

A few more details :
- The ########'s are NOT the same on each attempt to boot.
- When I try to reinstall Linux, I also got various error messages (Mosty "PANIC: attempted to kill init" or "PANIC: attempted to kill the idle task")
- Rescue mode fails the same way re-install does.

- For some reason I just can't explain I ONCE happened to manage to start the installer process, which unfortunately ended up hanging on "Detecting Network hardware". (I attempted to disable the onboard network device to no avail).