Check the PCI vendor and product ID strings on the output generated by the PCIinfo tool.
In my experience quite a few things can cause these strings to be misread - a ground cable not connecting properly (pushed out of the molex connector when attaching the power cable to a hard drive), low psu voltages, even a mis-shapen tower case, resulting in the mainboard being bowed. Seems unlikey given that the Voodoo3000 works though.
When dismantling, make sure the goldfingers of the pci card are still well embedded in the pci slot - when reassembling the case it is possible that these are being pulled out at the case flexes slightly. The i/o shield of the Voodoo 4500 may just be a different tolerance that the Voodoo 3000, causing it to sit further out of the PCI slot.
IIRC the Voodoo4 series draws a lot more power than the Voodoo3, perhaps your psu just cannot handle the extra power drain? You could try a different psu, or just try the Voodoo4 without the other PCI cards in place.
If all else fails, try the Voodoo 4 in a PC - see if it is working OK there.
