What is the magnitude of the spikes? I would expect that they would have to be a significant percentage (>10%?) of the DC voltage before they would show up on your logic analyzer. Also, what is the period?
Be sure to look at the impedance vs frequency curve of the decoupling caps. They may not be very effective at the problem frequency. Particularly when you consider that a transient pulse will have energy at a frequency much higher than the actual power supply switching frequency.
Check the board layout to make sure you the decoupling caps are well distributed, starting with some good bulk capacitance right next to where the power wires land on the board.
How much of the available current of the PC supply are you actually using? Some supplies are characterized assuming that a fair percentage of their power will be used. PC supplies are expecting to see a good deal of capacitance on the motherboard, where most of their power will be used by on-board regulators to drop their voltage to the 1 volt (sometimes less) that the CPU actully runs on. PC supplies are fairly cheep and good at their intended purpose, but can be pretty lousy when used elsewhere.