Originally posted by ReKleSS
And I'm pretty sure that the BIOS is set to PnP OS
I'm not quite sure I follow what you're saying -- is the PnP OS setting set to yes, or no? It sounds like it's set to yes; this is not where it should be. It should be set to no for best results with all devices (network cards are especially sensitive to this setting in Linux, but other devices may be as well).
Setting it to no really doesn't have anything to do with PnP. All that it does is make the BIOS initialize all devices. If it's set to yes, then the BIOS initializes "critical" devices only, and lets the OS initialize the rest. Well, this is redundant for one.
The other problem is, I don't have any idea how the BIOS decides whether or not a device is "critical". I would think that video cards would be, but some people have had problems with video cards that were solved by setting that to No, so their BIOSes obviously didn't agree with me.
In short, unless I misunderstood what you said, set it to no and see if that helps.